Next Greater Element Visualizer

How it works

1. Fill result with −1 and start with an empty stack of indices.
2. Scan i from left to right. While the stack is not empty and A[top] < A[i], pop top and set result[top] = A[i] — A[i] is the first larger value to its right.
3. Push i: it now waits for its own next greater element.
4. Indices still on the stack at the end have no larger value to their right and keep −1.

Worked example: [4, 5, 2, 25, 7, 8]

• i = 0, value 4: the stack is empty, so push 0. Waiting values: [4].
• i = 1, value 5: 4 < 5, so pop it — NGE(4) = 5. Push 1. Waiting: [5].
• i = 2, value 2: 5 ≥ 2, stop. Push 2. Waiting: [5, 2].
• i = 3, value 25: 2 < 25 → NGE(2) = 25; 5 < 25 → NGE(5) = 25. Push 3. Waiting: [25].
• i = 4, value 7: 25 ≥ 7, so just push 4. Waiting: [25, 7].
• i = 5, value 8: 7 < 8 → NGE(7) = 8; 25 ≥ 8, stop. Push 5. Waiting: [25, 8].
• End: 25 and 8 never met a larger value, so their answer is −1.

Result: [5, 25, 25, −1, 8, −1]. The stack stores indices (the values are shown here for readability), so each answer can be written to the right position in result — even when values repeat. This array is preloaded in the visualizer above.

Why it is O(n) and not O(n²)

The while loop inside the for loop looks quadratic, but count the work per element instead of per iteration: every index is pushed exactly once and popped at most once. That is at most 2n stack operations in total, so the whole scan is O(n) — an *amortized* argument. A decreasing input such as [5, 4, 3, 2, 1] never pops at all (n pushes; every index keeps −1), an increasing one pops once per step, and [5, 4, 3, 2, 1, 9] pops five indices in a single iteration — yet none of them exceeds 2n operations.

The stack stays monotonic: its values never increase from bottom to top. That is why one comparison with the top is enough — if A[i] is not larger than the top, it is not larger than anything below it either, because those values are bigger still.

The monotonic stack family

Change the comparison or the scan direction and the same loop answers related questions:

• Next greater (this page): pop while A[top] < A[i]; the stack is decreasing.
• Next smaller: pop while A[top] > A[i]; the stack is increasing.
• Previous greater or previous smaller: after the popping loop, whatever is left on top is the answer for i (−1 if the stack is empty).
• Strict vs non-strict: using <= instead of < decides how equal values are treated, which matters with duplicates.

Scanning right to left is an equally common variant: pop while A[top] <= A[i], and then the top, if any, is the next greater element of A[i].

Common mistakes

• Storing values instead of indices, so you can't tell which element was resolved, and duplicates get confused.
• Using <= when the problem asks for a *strictly* greater element, or the reverse.
• Forgetting the −1 default for elements that are never popped.
• Writing the answer to result[i] instead of result[top] — the popped index is the one being resolved.
• For a circular array (LeetCode 503), scanning only once: loop i from 0 to 2n − 1, read A[i % n], and push indices only during the first pass.

Interview variations

• Next Greater Element I (LeetCode 496): run this on nums2, store the answers in a hash map, then look up each value of nums1.
• Next Greater Element II (503): a circular array, handled with two passes.
• Daily Temperatures (739): store the distance i - top (days to wait) instead of the value.
• Online Stock Span (901): previous greater element, counted as a span.
• Largest Rectangle in Histogram (84): the previous and next *smaller* elements bound each bar.
• Trapping Rain Water (42), Sum of Subarray Minimums (907) and Remove K Digits (402) use the same stack.

Time and space complexity

Next Greater Element in Python

def next_greater(A):
    n = len(A)
    result = [-1] * n
    stack = []  # indices; their values decrease from bottom to top
    for i in range(n):
        while stack and A[stack[-1]] < A[i]:
            result[stack.pop()] = A[i]  # first larger value to the right
        stack.append(i)
    return result  # indices left on the stack keep -1


# next_greater([4, 5, 2, 25, 7, 8])  -> [5, 25, 25, -1, 8, -1]

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• Stack VisualizerInteractive stack visualizer: watch push, pop and peek move the top pointer of an array stack, see overflow and underflow happen, and learn why each is O(1).
• Deque VisualizerDeque visualizer: push and pop at both the front and back of a double-ended queue on a circular array, each in O(1), and see how it acts as a stack or a queue.
• Balanced Parentheses CheckerCheck if parentheses are balanced and watch the stack algorithm step by step: push each opener, match each closer, catch crossed or unclosed brackets in O(n).
• Postfix Expression EvaluatorEvaluate postfix (Reverse Polish) expressions with a stack, step by step: push numbers, pop two operands per operator in the right order, catch invalid input.
• Stack & Queue VisualizerStack and queue visualizer: animate push, pop, enqueue and dequeue, compare LIFO with FIFO, and step through circular queues, deques and stack applications.