Problem of The Day: Next Greater Element II

Problem Statement

Intuition

The problem is to find the next greater element for each element in a circular array. The first thought is to use a stack to maintain a decreasing sequence of indices corresponding to elements. This allows efficient determination of the next greater element as we traverse the array.

In a circular array, we need to iterate beyond the array’s bounds to ensure each element has a chance to check for a greater element that might wrap around. This can be achieved by traversing the array twice using modular arithmetic.

Approach

1. Initialize Variables:

   • res: An array initialized with -1 to store results.
   • stack: A stack to store indices of elements in the array.
   • Traverse the array twice (using 2 * N - 1 iterations).

2. Iterate in Reverse:

   • Use the modulo operator (i % N) to handle the circular nature of the array.
   • For each element:
     • Remove indices from the stack whose corresponding values are less than or equal to the current element (nums[index]).
     • If the stack is not empty, the top of the stack gives the next greater element.
     • Otherwise, the result remains -1.

3. Update the Stack:

   • Add the current index to the stack to maintain the decreasing sequence.

4. Return Result:

   • After processing all elements, return the res array containing the next greater elements.

Complexity

• Time Complexity:
  \(O(n)\)
  Each element is pushed onto the stack once and popped at most once. Since we iterate through the array twice, the overall complexity is linear relative to the array size.

• Space Complexity:
  \(O(n)\)
  The stack can hold up to n indices in the worst case.

Code

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        N = len(nums)
        stack = []
        res = [-1] * N
        for i in range(2 * N - 1, -1, -1):
            index = i % N
            while stack and nums[stack[-1]] <= nums[index]:
                stack.pop()
            if stack:
                res[index] = nums[stack[-1]]
            else:
                res[index] = -1

            stack.append(index)
        return res