Stacks & queues

Next greater element · source
1function nextGreater(a: number[]) {
2 const res = new Array(a.length).fill(-1);
3 const stack: number[] = [];
4 for (let i = 0; i < a.length; i++) {
5 while (stack.length && a[stack.at(-1)!] < a[i]) {
6 res[stack.pop()!] = a[i];
7 }
8 stack.push(i);
9 }
10 return res;
11}
Next greater element · liveA stack of values still waiting for something bigger.
stack · bottom → topempty

Scan left to right. The stack holds indices still waiting for a greater element.

1 / 39

How next greater element works

For every element, find the first element to its right that is larger. Brute force checks every pair — O(n²). The stack version scans once: each index waits on the stack until a bigger value arrives, and the moment it does, the wait is over — pop and record the answer. Elements still on the stack at the end never met anything bigger; they keep −1.

The magic invariant: values on the stack never increase from bottom to top (equal values wait together — only a strictly greater arrival resolves them). Why? Anything smaller than the incoming value gets popped before the push. So the stack is exactly the set of elements whose answer is still unknown, ordered by when they will give up. Watch the chip strip — it never violates the ordering.

The complexity argument interviewers want to hear: each index is pushed once and popped at most once, so the whole scan is ≤ 2n stack operations — O(n) amortized, even though a single step can pop many times. This pattern (daily temperatures, stock span, next smaller element) is one of the most reused templates in interviews — recognize “nearest larger/smaller to the left/right” and reach for it.

space play / pause · ←→ step

Complexity

timeO(n)
spaceO(n)
patternmonotonic stack
stack ops≤ 2n total