Coding interview problems › Stack & Monotonic Stack

📚 Stack & Monotonic Stack Easy

Next Greater Element

Next Greater Element explained: a monotonic stack finds the first larger value to the right of every element in O(n). Tested Python, pitfalls and a live visual.

Also searched as: next greater element using stack · NGE problem · next larger element to the right

📚

Try it live Free

Stacks & the Monotonic Stack

Open the monotonic stack mode and step through: each waiting element pops off the instant a bigger one arrives, which is the moment its next greater element is found.

Open the playground →

The problem

For each element of a list of integers, find the first element to its right that is strictly larger. Return a list of those values, using -1 where no larger element exists.

Inputnums = [4, 5, 2, 25, 7]
Output[5, 25, 25, -1, -1]
Inputnums = [9, 7, 3]
Output[-1, -1, -1]

The key insight

Elements that have not found their answer yet sit on a stack, and their values are decreasing from bottom to top. A new value is the answer for every smaller element on top of the stack, so pop those and record it. Each element waits on the stack exactly until its answer arrives.

Brute force first: A nested loop that scans right from every position takes O(n²) time.

Step-by-step approach

  1. Create result = [-1] * n and an empty stack of indices.
  2. Scan the list left to right with index i.
  3. While the stack is not empty and nums[stack[-1]] < nums[i], pop index j and set result[j] = nums[i].
  4. Push i.
  5. Anything still on the stack at the end has no greater element and keeps -1.

Python solution

PYTHON 3tested
def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                          # indices still waiting for an answer
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x     # x is the first larger value to the right
        stack.append(i)
    return result

Complexity

TimeO(n)
SpaceO(n)

Each index enters and leaves the stack at most once, so the total work across all iterations of the inner loop is O(n).

Common mistakes

Frequently asked questions

What is the time and space complexity of Next Greater Element?

O(n) time, since each element is pushed and popped at most once, and O(n) space for the stack.

How do I handle a circular array?

Loop i from 0 to 2n - 1 and use nums[i % n], but only push indices during the first pass. Elements near the end can then find a greater element at the start.

How do I find the next smaller element instead?

Flip the comparison: pop while the top is greater than the current value. The stack then keeps increasing values.

What about the previous greater element?

Scan the same way, but before pushing i, the element on top of the stack (after popping smaller ones) is the previous greater element of i.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Stack & Monotonic Stack Stacks & the Monotonic Stack lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.