Next Greater Element

Table of Contents +

This one looks simple. For each number in an array, you just look to its right and pick the first bigger number. Easy, right? But the interviewer is not asking you to find the answer. They want to see if you can find it fast. The slow way is obvious. The fast way needs a stack, and that is what they are really testing.

🔎 The Problem

You are given an array of numbers. For every element, find the next element on its right that is greater than it. If there is no greater element on the right, the answer for that position is -1.

Look at this example.

Input:  [4, 5, 2, 25]
Output: [5, 25, 25, -1]

So for 4, the next bigger number on the right is 5. For 5, it is 25. For 2, it is 25 again. And 25 has nothing bigger on its right, so it gets -1.

🐢 The Brute-Force Way

The first idea that comes to mind is simple. For each element, walk through everything on its right and stop at the first number that is bigger. If you reach the end and find nothing, put -1.

This works. But see the problem. You have an outer loop for every element, and an inner loop that scans the rest of the array. That is a loop inside a loop. For a big array this becomes slow. We call this O(n²) time, which means the work grows with the square of the array size.

In an interview, you can mention this approach to show you understand the problem. Then you say “but we can do better” and move to the stack.

📚 The Optimal Way: A Monotonic Stack

Here is the key idea. We walk through the array from right to left. We keep a stack that holds the numbers we have seen so far on the right side. But not all of them. We only keep the numbers that could still be an answer for something on the left.

A stack is a structure where you add and remove from the same end, like a pile of plates. The one you put last is the one you take first.

Now think about it like this. Say you are standing at some number and looking right. Any number on the right that is smaller than a number even further right is useless to you. Why? Because the bigger one blocks it. If a small number cannot beat the current value, and there is a bigger number sitting behind it, that small number will never be anyone’s answer going forward. So we throw it away.

That is why we keep a monotonic decreasing stack. Monotonic decreasing means the values in the stack go from big at the bottom to small at the top. Every time a new number comes in, we pop off all the smaller numbers from the top, because they can no longer help anyone.

Steps to solve it

  1. Create an empty stack and an answer array filled with -1.
  2. Walk through the array from the last index to the first.
  3. For the current number, pop the stack while the top is less than or equal to the current number. Those values are blocked, so remove them.
  4. After popping, if the stack is not empty, the top is the next greater element. Put it in the answer. If the stack is empty, the answer stays -1.
  5. Push the current number onto the stack so it can be a candidate for elements on its left.

Let me show this in all five languages.

This Python version uses a plain list as the stack, where append pushes and pop removes from the end.

next_greater.py
def next_greater(arr):
    n = len(arr)
    result = [-1] * n   # default answer is -1
    stack = []          # holds candidate values from the right


    for i in range(n - 1, -1, -1):
        # Pop values that cannot beat the current one
        while stack and stack[-1] <= arr[i]:
            stack.pop()
        # Whatever is left on top is the next greater element
        if stack:
            result[i] = stack[-1]
        # Current value becomes a candidate for the left side
        stack.append(arr[i])
    return result




arr = [4, 5, 2, 25]
print(next_greater(arr))

The output of the above code will be:

[5, 25, 25, -1]

You might worry that the inner while loop makes this slow too. But look closer. Each number is pushed onto the stack once and popped at most once. So across the whole run, the total push-and-pop work is just n. That is what makes it O(n), one straight pass.

⏱️ Time and Space Complexity

Approach Time Space
Brute force (nested loops) O(n²) O(1)
Monotonic stack O(n) O(n)

The stack uses some extra memory. But in return you turn a slow O(n²) solution into a fast O(n) one. In most interviews that trade is exactly what they want to see.

Tip

If the interviewer asks for the next greater element to the left instead, the trick is the same. Just walk the array from left to right instead of right to left. The stack logic does not change at all.

🧩 Key Takeaways

  • ✅ The brute-force way uses a loop inside a loop, which is O(n²) and slow for big inputs.
  • ✅ A monotonic decreasing stack solves it in one pass, giving you O(n) time.
  • ✅ The stack keeps only useful candidates. Smaller numbers get popped because a bigger one already blocks them.
  • ✅ Each element is pushed once and popped once, so the total work stays linear.
  • ✅ Walk right to left for “next greater on the right”, and left to right for “next greater on the left”.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What is the time complexity of the optimal monotonic stack solution?

    Why: Each element is pushed and popped at most once, so the total work is linear in the array size.

  2. 2

    Why do we pop smaller values off the stack when a new number arrives?

    Why: Once a bigger number blocks a smaller one, that smaller value is useless for any element further left.

  3. 3

    For the array [4, 5, 2, 25], what is the next greater element of 2?

    Why: Scanning right from 2, the first number greater than 2 is 25.

  4. 4

    To find the next greater element on the LEFT instead, what changes?

    Why: The stack logic stays the same; you only flip the direction of the traversal.

Score: 0 / 4

🚀 What’s Next?

Previous Valid Parentheses Next Min Stack

Share & Connect

Share on LinkedIn