mediumCodingConceptMidSenior
For each element of an array, find the first element to its right that is larger. State the invariant your stack maintains.
4 min readUpdated 2026-08-15
Answer
Short answer
Scan left to right holding a stack of indices whose answers are still unknown, kept strictly decreasing by value. Each new element resolves and pops everything smaller than it, then pushes itself.
Was this answer helpful?
Likely follow-ups
- Change it to the next greater-or-equal element. Which character moves?
- Now the array is circular. How do you adapt the same scan?
- Largest rectangle in a histogram uses this technique. What is the invariant there, and why the sentinel?
- Could you scan right to left instead, and what would the stack hold then?
Related questions
- Find the largest rectangle in a histogram in linear time, and tell me what the stack holds at every step.hardAlso on monotonic-stack and stacks5 min
- Return the maximum of every window of size k as it slides across the array. Why a deque, and what is the invariant?hardAlso on amortised-analysis and arrays5 min
- Implement a FIFO queue using only two stacks, then tell me what a dequeue costs.mediumAlso on stacks and amortised-analysis4 min
- Appending to a dynamic array is O(1) amortised. Derive that, then defend it against someone who points out that a single append copies the whole array.mediumAlso on amortised-analysis5 min