Next Greater Element | Optimal Solution using Stack

Given an array arr[ ] of integers, the task is to find the next greater element for each element of the array in order of their appearance in the array. Next greater element of an element in the array is the nearest element on the right which is greater than the current element.
If there does not exist next greater of current element, then next greater element for current element is -1. For example, next greater of the last element is always -1.

Here’s the [Problem Link] to begin with.

Examples

Input: arr[] = [1, 3, 2, 4]
Output: [3, 4, 4, -1]
Explanation: The next larger element to 1 is 3, 3 is 4, 2 is 4 and for 4, since it doesn't exist, it is -1.

Input: arr[] = [6, 8, 0, 1, 3]
Output: [8, -1, 1, 3, -1]
Explanation: The next larger element to 6 is 8, for 8 there is no larger elements hence it is -1, for 0 it is 1 , for 1 it is 3 and then for 3 there is no larger element on right and hence -1.

Input: arr[] = [10, 20, 30, 50]
Output: [20, 30, 50, -1]
Explanation: For a sorted array, the next element is next greater element also except for the last element.

Input: arr[] = [50, 40, 30, 10]
Output: [-1, -1, -1, -1]
Explanation: There is no greater element for any of the elements in the array, so all are -1.

Constraints:
1 ≤ arr.size() ≤ 10⁶
0 ≤ arr[i] ≤ 10⁹

Brute Force Approach (Naive Nested Loops)

Intuition

Check every pair: for each element, scan to its right and return the first larger number. If nothing found, use -1. This is how most beginners start and helps cement the purpose of the problem.

Detailed Approach

• For each position i (from 0 to n-1):
  • Loop from j = i+1 to n-1
  • If arr[j] > arr[i], set ans[i] = arr[j] and break
• If inner loop finds no such j, ans[i] remains -1.

Code

class Solution:
    def nextLargerElement(self, arr):
        n = len(arr)
        ans = [-1] * n    # Initialize all answers as -1
        for i in range(0, n):
            # Check for greater element towards right of arr[i]
            for j in range(i + 1, n):
                if arr[j] > arr[i]:
                    ans[i] = arr[j]   # Set the NGE for arr[i]
                    break   # Stop at the first greater element
        return ans

Code Explanation

• Simple double loop; the outer loop is for each element, the inner for searching the next greater.
• If a next greater is found, update the answer and move to the next element.

Dry Run

arr = [4, 5,5]

• For 4: Next greater is 5
• For 5: Next greater is 25
• For 2: Next greater is 25
• For 25: No greater; -1

Result: [5, 25, 25, -1]

Time and Space Complexity

• Time: O(n²) – the outer loop runs n times, and the inner up to n times per iteration.
• Space: O(n) – for the result array.

Simplified

The intuition is clear, but the approach is inefficient for large arrays due to repeated scanning.

Optimal Approach (Monotonic Stack)

Intuition

Process elements from right to left (since we’re looking for the first greater on the right). Use a stack to keep “potential” NGEs: for each element, pop all smaller or equal values from the stack; for the first bigger value (if the stack is not empty), that’s the NGE!

Detailed Approach

• Initialize stack and result array (all -1s).
• Traverse array backward (right to left):
  • While stack is not empty and stack top <= arr[i], pop stack.
  • If stack not empty, result[i] = stack[-1]
  • Push arr[i] onto stack

Code

class Solution:
    def nextLargerElement(self, arr):
        n = len(arr)
        result = [-1] * n    # Initialize all answers as -1
        stack = []           # Stack to store potential NGEs
        
        for i in range(n - 1, -1, -1):
            # Remove elements not greater than arr[i]
            while len(stack) != 0 and stack[-1] <= arr[i]:
                stack.pop()
                
            # If stack is not empty, assign top as NGE
            if len(stack) != 0:
                result[i] = stack[-1]
            # Push current element to stack for future comparisons
            stack.append(arr[i])
        return result

Code Explanation

• By going right to left, we always maintain the stack as “decreasing” from top to bottom.
• For every element, we efficiently find its NGE or confirm it’s -1.
• Each element is pushed and popped at most once, thanks to the stack.

Dry Run

arr = [4,5]

• Start at 25, push to stack, NGE = -1
• For 2, stack top is 25 > 2, so NGE = 25; push 2
• For 5, pop 2 because 2 < 5, now top is 25, NGE = 25
• For 4, stack top is 5 > 4, so NGE = 5

Results: [5, 25, 25, -1]

Time and Space Complexity

• Time: O(n) – each element is pushed and popped at most once, making it linear in total.
• Space: O(n) – used for the stack and result array.

Simplified

A classic use of the stack for array problems; fast, elegant, and crucial for interviews!

Summary Table

Conclusion

The Next Greater Element problem is a canonical example of how stacks can convert quadratic brute force into linear time. Always start with brute force for intuition, but be sure to master the stack-based approach for efficient, scalable solutions in coding interviews!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.