For each element, finds the first larger value to its right using a monotonic stack of indices that are still waiting for their answer. Each index is pushed and popped at most once.
For each element, finds the first larger value to its right using a monotonic stack of indices that are still waiting for their answer. Each index is pushed and popped at most once.
Time complexity: O(n). Space complexity: O(n).
Core idea — Keep a stack of indices whose next-greater element hasn't been found yet, ordered so their values decrease from bottom to top.
What each pass accomplishes — When a new value is larger than the value on top of the stack, it is that index's next greater element — pop and record it, repeating until the top is bigger. Then push the new index. Every index enters and leaves the stack once, giving O(n).
Use the interactive visualizer above to run Next Greater Element on your own input and watch every comparison, swap, and operation animate step by step — pause, scrub, or replay at any speed.