Next Greater Element (Right) using Stack

Welcome back to Day 3 of our DSA Problem Series, where we explore one problem each day, understand its logic, and break it down into clean Java code.

Today’s challenge is a classic stack-based problem —
👉 Find the Next Greater Element on the Right (NGE) for every element in the array.

Problem Statement

Given an array of integers, for every element, find the next greater element that appears to its right.
If there’s no greater element, store -1 for that position.

Example:
Input: [ 4, 5, 2, 10, 8 ]
Output: [ 5, 10, 10, -1, -1 ]

Explanation:

• For 4, next greater is 5
• For 5, next greater is 10
• For 2, next greater is 10
• For 10, no greater element → -1
• For 8, no greater element → -1

Brute Force Thought

A straightforward approach would be:

For each element, look to its right until you find a greater number.
But that gives O(n²) time complexity — not ideal for large arrays 😓

We can do better with a stack.

Optimized Stack-Based Solution (O(n))

public static int[] nextGreator(int[] arr) {
    Stack<Integer> st = new Stack<>();
    int[] result = new int[arr.length];

    for (int i = arr.length - 1; i >= 0; i--) {
        // Pop smaller or equal elements from stack
        while (!st.isEmpty() && arr[i] >= arr[st.peek()]) {
            st.pop();
        }

        // If stack is empty, no greater element to the right
        result[i] = st.isEmpty() ? -1 : arr[st.peek()];

        // Push current index onto the stack
        st.push(i);
    }
    return result;
}

How this approach works...

1. Idea:
   
   Use a stack to keep track of elements for which we have not yet found the next greater element. Traverse the array from right to left so that the elements to the right are already processed.

2. Step-by-Step:

   • Initialize an empty stack and a result array.
   • For each element (starting from the end of the array):
     1. Pop smaller elements from the stack, because they cannot be the next greater for the current element.
     2. If the stack is empty after popping, there is no greater element to the right — store -1.
     3. If the stack is not empty, the element at the top of the stack is the next greater element — store it in the result.
     4. Push the current element (or its index) onto the stack for future comparisons.

3. Why it works:

   • The stack always contains elements that are potential candidates for next greater elements of elements to their left.
   • Each element is pushed and popped at most once, giving an efficient O(n) solution.

Step-by-Step Dry Run

Let’s dry-run it for arr = [4, 5, 2, 10, 8].

i	arr[i]	Stack (indices)	Next Greater	Result[]
4	8	[]	-1	[-,-,-,-,-1]
3	10	[4]	-1	[-,-,-,-1,-1]
2	2	[3]	10	[-,-,10,-1,-1]
1	5	[3]	10	[-,10,10,-1,-1]
0	4	[1,3]	5	[5,10,10,-1,-1]

Output: [5, 10, 10, -1, -1]

Time and Space Complexity comparison

Operation	Description	Complexity
Traversal of array	Each element is visited once (from right to left)	O(n)
Stack operations (push/pop)	Each element is pushed and popped at most once	O(n)
Total Time Complexity	Traversal + Stack operations	O(n)
Space Complexity	Stack + Result array	O(n)

Final Thoughts

This problem forms the base for many variations like:

• Next Greater Element (Left)
• Next Smaller Element (Right/Left)
• Stock Span Problem
• Largest Rectangle in Histogram

So make sure you truly understand this one — it’ll come in handy often!

Your Turn!

Try modifying the code for:

🔁 Next Smaller Element (Right)

Can you spot the small change needed? 😉

Bonus Challenge:
Also, try writing the brute force solution and analyze its time complexity.
Can you explain why the stack-based approach is faster?

💬 Share your version or your reasoning in the comments below — We'd love to see how you approach it!