Next greater element and the monotonic stack
“For each element, find the next element to its right that is greater. What is the right approach, and why is it O(n) even though it has a nested loop?”
What this tests
- Whether the candidate recognizes the "nearest element with property" signal for a monotonic stack.
- Whether they can perform an amortized analysis honestly rather than hand-waving.
- Ability to state the stack invariant.
- Knowledge of variants: next smaller, previous greater, circular arrays, histogram.
Strong answer
The brute force checks every j > i for each i: O(n^2). The inefficiency is that once a large element appears, every smaller element before it that is still waiting gets the same answer simultaneously, yet the brute force re-scans for each. A Monotonic Stack captures the waiting elements: scan left to right, keep a stack of indices whose values are strictly decreasing from bottom to top. When the current value is greater than the top, the top has found its answer — pop it, record current, and repeat. Then push the current index.
The invariant: the stack always contains exactly the elements that have not yet seen a greater element, in decreasing value order. That order is what makes popping correct: if the current value beats the top, it may beat elements below too, and the loop checks them; if it does not beat the top, it cannot beat anything below, so the loop stops correctly.
The complexity argument is amortized: the inner while loop looks quadratic, but each index is pushed exactly once and popped at most once. Total pushes plus pops is at most 2n, so the whole scan is O(n) regardless of how many pops any single iteration performs. A strong candidate states this as "charge each pop to the push that created it" rather than saying "usually it's fast".
Green flags · Red flags
- Identifies "nearest greater/smaller to the left/right" as the pattern signal.
- States the invariant (decreasing stack, unresolved elements only).
- Explains amortized
O(n)via each element pushed once and popped at most once. - Knows the variants: previous greater by scanning direction, next smaller by flipping the comparison, circular by scanning
2n. - Connects to largest rectangle in histogram and daily temperatures.
- Says the nested loop is
O(n^2), or says it isO(n)"because it is usually fast". - Keeps values in the stack when indices are required for distances.
- Uses
>=vs>inconsistently and cannot say how duplicates should be resolved. - Cannot explain why elements below the top need not be checked when the top is not popped.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.