Problem Description

• 503. Next Greater Element II

The "Next Greater Element II" problem asks you to find the next greater element for each element in a circular array. For each element, you need to find the first element that is greater than it when traversing the array in a circular manner.

Key Points:

• The array is treated as circular (last element connects to first)
• For each element, find the next greater element in circular order
• If no greater element exists, return -1 for that position
• The result should be in the same order as the input array

Example: [1, 2, 1]

• For 1 at index 0: Next greater is 2 at index 1
• For 2 at index 1: Next greater is -1 (no element > 2)
• For 1 at index 2: Next greater is 2 at index 1 (circular)
• Result: [2, -1, 2]

Algorithm Walkthrough

This solution uses a monotonic decreasing stack with a clever two-pass approach to handle the circular nature of the array.

Core Strategy

1. First Pass: Pre-populate the stack with all elements (reverse order)
2. Second Pass: Process each element to find its next greater element

Detailed Steps

Step 1: Initialize Stack (First Pass)

for(int i=nums.length-1; i>=0; i--){
    stack.push(nums[i]);
}

• Traverse array from right to left
• Push all elements onto the stack
• This simulates having "seen" all elements in circular order

Step 2: Find Next Greater Elements (Second Pass)

for(int i=nums.length-1; i>=0; i--){
    int number = nums[i];
    while(!stack.isEmpty() && stack.peek() <= nums[i]){
        stack.pop();
    }
    nums[i] = stack.empty() ? -1 : stack.peek();
    stack.push(number);
}

For each element (right to left):

1. Store current value: number = nums[i]
2. Pop smaller elements: Remove all stack elements ≤ current element
3. Find result: Top of stack is the next greater element (or -1 if empty)
4. Update stack: Push current element for future processing

Why This Works

Monotonic Stack Property: The stack maintains elements in decreasing order from bottom to top. When we encounter an element, we:

• Remove all smaller/equal elements (they can't be "next greater" for anything)
• The remaining top element is the next greater element
• Add current element to maintain the decreasing property

Circular Handling: The initial population of the stack ensures that when processing element at index i, the stack contains all elements that could potentially be the "next greater" in circular order.

Example Trace

For [1, 2, 1]:

After first pass: Stack = [1, 2, 1] (bottom to top)

Second pass:

• i=2, nums[2]=1: Stack top is 1, pop it. Stack top is 2. Result: nums[2]=2
• i=1, nums[1]=2: Stack top is 2, pop it. Stack empty. Result: nums[1]=-1
• i=0, nums[0]=1: Stack top is 2. Result: nums[0]=2

Final result: [2, -1, 2]

Complexity Analysis

Time Complexity: O(n)

• First pass: O(n) to populate stack
• Second pass: O(n) amortized
  • Each element is pushed exactly once
  • Each element is popped at most once
  • Total pushes + pops = 2n operations
• Overall: O(n)

Space Complexity: O(n)

• Stack space: In worst case (decreasing array), stack stores all n elements
• Input modification: Uses input array for output (no additional result array)

Full Solution

The solution elegantly handles the circular array constraint by using a two-pass approach with a monotonic stack. The key insight is that by pre-populating the stack with all elements, we ensure that when processing any element, the stack contains all potential "next greater" candidates in the correct order. This transforms a potentially complex circular traversal into a straightforward linear algorithm with optimal time complexity.

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        // TC:O(n)
        // SC:O(n)
       Stack<Integer> stack=new Stack<>();
        for(int i=nums.length-1;i>=0;i--){
            stack.push(nums[i]);
        }

        for(int i=nums.length-1;i>=0;i--){
            int number=nums[i];
                while(!stack.isEmpty() && stack.peek()<=nums[i]){
                    stack.pop();
                }

            nums[i]=stack.empty()?-1:stack.peek();
            stack.push(number);
        }

        return nums;
    }
}