Next Greater Element

Time: O(n)

Space: O(n)

Intuition

Monotonic stack: maintain a decreasing stack. For each element, pop all elements smaller than it â€” the current element is their "next greater". Elements left in the stack have no next greater â†’ assign -1.

Algorithm

1Stack of indices. result[n]=-1.
2For i from 0 to n-1: while stack not empty and arr[stack.top] < arr[i]: result[stack.pop()] = arr[i].
3Push i.

Example Walkthrough

Input: arr = [4,5,2,25]

1.i=0: push 0. i=1: 4<5 â†’ result[0]=5. Push 1.
2.i=2: push 2. i=3: 2<25 â†’ result[2]=25. 5<25 â†’ result[1]=25. Push 3.
3.result=[5,25,25,-1].

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

Common Pitfalls

•The stack stores INDICES, not values â€” you need the index to update result[].

Next Greater Element.java

Java

// Approach: Monotonic stack. Process array right to left; for each element pop smaller elements from stack.
// Time: O(n) Space: O(n)
class Solution {
    // Function to find the next greater element for each element of the array.
    public ArrayList<Integer> nextLargerElement(int[] arr) {
        ArrayList<Integer> ans = new ArrayList<>(Collections.nCopies(arr.length, -1));
        Stack<Integer> s = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            while (!s.isEmpty() && arr[s.peek()] < arr[i])
                ans.set(s.pop(), arr[i]);

            s.push(i);
        }
        return ans;
    }
}

Was this solution helpful?