Next greater price with a monotonic stack
Asked at Citadel, DE Shaw
For each price in a series, find the next price after it that is strictly higher; report -1 if none exists. (The classic "when does the price next improve?" question.)
prices = [4, 2, 5, 1, 3]
-> [5, 5, -1, 3, -1]
Return the list of next-greater values. Aim for , the nested-loop scan is .
Show a hint
Keep the indices still waiting for a higher price. When a new price arrives, which of the waiting ones can now be resolved, and in what order do they sit?
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.