Next - Larger - Element

Problem Link

Next Larger Element – GeeksforGeeks

Problem Statement

Given an array A of size N, the task is to find the next greater element for each element of the array in order of their appearance in the array.

For an element A[i], the next greater element is the first element A[j] such that:

• j > i, and

• A[j] > A[i]

If no such element exists, output -1 for that index.

Examples

Example 1:

Input: 
N = 4
A = [1, 3, 2, 4]

Output: 
3 4 4 -1

Explanation:
Next greater elements:
1 → 3
3 → 4
2 → 4
4 → -1

Example 2:

Input: 
N = 5
A = [6, 8, 0, 1, 3]

Output: 
8 -1 1 3 -1

Constraints

• 1 <= N <= 10⁶

• 1 <= A[i] <= 10¹⁸

Intuition

We need to find the next greater element for each item. A brute-force approach would use nested loops, which is inefficient for large arrays.

Instead, we use a monotonic stack (a stack that stores elements in decreasing order) to efficiently keep track of elements and find their next greater elements in O(n) time.

Approach: Monotonic Stack (Right-to-Left Traversal)

1. Traverse the array from right to left.

2. Use a stack to keep track of candidates for the next greater element.

3. For each element:

   • While the stack is not empty and the top of the stack is less than or equal to the current element, pop it.

   • If the stack is empty after popping, there is no greater element → store -1.

   • Else, the stack top is the next greater element.

4. Push the current element onto the stack.

5. Finally, reverse the result to match the original array order.

Java Code

class Solution {
    public static long[] nextLargerElement(long[] arr, int n) {
        Stack<Long> stack = new Stack<>();
        long[] result = new long[n];

        for (int i = n - 1; i >= 0; i--) {
            long curr = arr[i];
            while (!stack.isEmpty() && stack.peek() <= curr) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(curr);
        }

        return result;
    }
}

Time and Space Complexity

Dry Run

Input:

arr = [1, 3, 2, 4]

Stack Trace:

• i=3, 4 → Stack: [], Result[3] = -1, push 4

• i=2, 2 → Stack: [4], Result[2] = 4, push 2

• i=1, 3 → Stack: [4, 2] → pop 2, Result[1] = 4, push 3

• i=0, 1 → Stack: [4, 3], Result[0] = 3, push 1

Output:

[3, 4, 4, -1]

Conclusion

This is a classic stack-based pattern problem that teaches how to use monotonic stacks to solve next greater/smaller type problems efficiently.

Useful variations include:

• Next Smaller Element

• Previous Greater Element

• Stock Span Problem