Next greater element
Scenario
You are tracking daily stock prices and want to know how many days you have to wait for a higher price.
How do you find the next greater price efficiently without comparing every day to every future day?
Why it exists
Problem: Given an array, we want to map each element to the first element to its right that is strictly larger. A brute force scan for every element takes O(n^2) time.
Naive approach: Scan forward from every element to find its next greater — O(n^2) nested loops.
Better idea: Use a monotonic decreasing stack to act as a waiting line. Array indices wait on the stack until a larger element arrives and resolves their query, reducing time complexity to O(n).
Mental model
Small people wait in line. When a tall person arrives, all the smaller people in front of them immediately see them and leave the line.
Traverse the array from left to right. Maintain a stack of indices for elements that haven't found their next greater element yet. Because we pop whenever a larger element arrives, the stack naturally stays in decreasing order. When we pop an index, we know the current element is its 'next greater'. Any indices left on the stack at the end have no greater element to their right and default to -1.
Repeated decision: While the stack is non-empty and the current element is greater than the element at the top index: pop the index and record the current element as its answer.
Explanation
Next Greater Element is the canonical problem for applying the monotonic stack pattern. It directly maps to the algorithm's mechanical strengths: elements sit in a decreasing state until they are shattered by a larger arrival.
A powerful extension of this problem is the circular array variant. Rather than concatenating two arrays together in memory (which costs O(n) space overhead), a virtual double-pass is executed by running the loop to 2n and accessing elements via `i % n`. The stack logic remains completely oblivious to the circular trick.
For circular arrays, we can simulate concatenating the array to itself by iterating up to `2n-1` and using the modulo operator (`i % n`) to map back to valid bounds. This works perfectly because each real index resolves its next greater element at most once, and the stack handles the wrap-around naturally.
Key points
- Invariant: The stack keeps track of elements waiting for a greater element. A new larger element resolves them.
- Complexity: O(n) amortized time, processing each element linearly.
- Recognition cue: Problems asking for the 'next largest' or 'first element greater than X to its right'.
Pattern: Monotonic Decreasing Stack
Recognition cues:
- Find the 'next greater', 'next warmer', or 'nearest larger' element to the right.
Failure signals
- Looking for absolute maximums instead of relative next greater elements.
Engineering examples
Signal Processing Thresholds
Finding the next timestamp where a sensor reading exceeds a critical threshold
Efficiently maps thousands of data points to their nearest future spikes in linear time.
Common mistakes
- Simulating circular arrays with memory bloat: If the array is circular, don't allocate a new array of double the length. Iterate up to 2n and use modulo arithmetic `i % n` to wrap around.
- Not using a pre-allocated result array: Since elements are resolved out of order (popping from the stack), you must initialize a result array with default values (-1) and place answers into specific indices.
Recall questions
- What happens to indices that remain on the stack after the entire array is traversed?
- How do you efficiently handle a circular 'Next Greater Element' problem without doubling the array allocation?
- What condition triggers a pop from the stack in this algorithm?
Questions & answers
Find the Next Greater Element for each element in an array.
Initialize a result array with -1. Use a decreasing monotonic stack of indices. When `arr[i] > arr[stack.top()]`, pop and set `result[popped_index] = arr[i]`. Push `i`.
Approach: Standard NGE template.
Find the Next Greater Element in a circular array.
Iterate `i` from 0 to 2n-1. Access elements via `arr[i % n]`. Use the identical monotonic stack logic.
Approach: Virtual double-pass using modulo.
Continue learning
Previous: Monotonic stack
Related: Monotonic stack