Next Greater Element Ii - Leetcode Solution

The Next Greater Element II problem on LeetCode asks us to find the next greater element for each element in a given array, but with the constraint that the array is circular. This means that the next greater element for the last element in a circular array is the first element in the same array. Similarly, the next greater element for the previous element of the first element is the last element in the array.

To solve this problem, we can use a stack to keep track of elements. We traverse the array twice to make it circular (i.e., we concatenate the array with itself). In the first traversal, we push each element of the array onto the stack. For each element, we check if the current element is greater than the top element of the stack. If it is, then we pop the stack and mark the popped element's next greater element as the current element. We do this until we find an element greater than the current element or the stack becomes empty. We continue this process until the end of the first traversal.

In the second traversal, we follow a similar process, but this time we mark the last element as the next greater element for any element still remaining in the stack. This is done to handle the circular nature of the array. We then return the next greater elements for each element in the original array.

Here is the implementation in Python:

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        stack = []
        result = [-1] * n
        for i in range(n * 2):
            while stack and nums[i % n] > nums[stack[-1]]:
                result[stack.pop()] = nums[i % n]
            stack.append(i % n)
        return result

The time complexity of this solution is O(n) since we traverse the array twice and push/pop each element onto/from the stack at most once. The space complexity is also O(n) since we need to store all elements in the stack.

1