A price-history chart shows, for each day, how many later days had a strictly lower price, to tell shoppers whether waiting usually pays off. The daily prices are in prices.
Write laterCheaper(prices) that returns an array where item i is the number of indexes j > i with prices[j] < prices[i]. Aim for O(n log n) time.
Input: prices = [8,3,9,3,1] Output: [3,1,2,1,0]
After 8 come 3, 3, and 1, all cheaper. After the first 3, only 1 is cheaper (the other 3 is equal, not lower).
Input: prices = [1,2,3] Output: [0,0,0]
Prices only go up, so no later day is cheaper.
0 <= prices.length <= 10^5-10^9 <= prices[i] <= 10^9Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #95 Later Cheaper Prices. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.