Medium · Monotonic Stack
Understand → Visualise → Practice.
For each value, which is the first value to its right that is bigger? Checking everything to the right is O(n²).
Keep a stack of indices still waiting for an answer, with values decreasing from bottom to top. A bigger value answers everything smaller on top.
The current value may answer waiting ones.
Each popped index gets the current value.
It now waits for its own answer.
O(n) time: every index is pushed once and popped at most once. O(n) space.
Store indices on the stack, not values, so you know where to write each answer.
Read the full guides first: Stacks, Queues and Deques.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.