Research

[LeetCode 503] Next Greater Element II

Given a circular integer array nums (i.e., the next element of nums[nums.length - 1] is nums[0]), return the next greater number for every element in nums.

The next greater number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, return -1 for this number.

Example 1:

Input: nums = [1,2,1]
Output: [2,-1,2]
Explanation: The first 1's next greater number is 2; 
The number 2 can't find next greater number. 
The second 1's next greater number needs to search circularly, which is also 2.

Example 2:

Input: nums = [1,2,3,4,3]
Output: [2,3,4,-1,4]

Constraints:

  • 1 <= nums.length <= 104
  • -109 <= nums[i] <= 109

Approach Using Stack [Accepted]

This approach makes use of a stack. This stack stores the indices of the appropriate elements from nums array. The top of the stack refers to the index of the Next Greater Element found so far. We store the indices instead of the elements since there could be duplicates in the nums array. The description of the method will make the above statement clearer.

We start traversing the nums array from right towards the left. For an element nums[i] encountered, we pop all the elements stack[top] from the stack such that nums\big[stack[top]\big] \leq nums[i]. We continue the popping till we encounter a stack[top] satisfying nums\big[stack[top]\big] > nums[i]. Now, it is obvious that the current stack[top] only can act as the Next Greater Element for nums[i] (right now, considering only the elements lying to the right of nums[i]).

If no element remains on the top of the stack, it means no larger element than nums[i] exists to its right. Along with this, we also push the index of the element just encountered(nums[i]), i.e. i over the top of the stack, so that nums[i] (or stack[top]) now acts as the Next Greater Element for the elements lying to its left.

We go through two such passes over the complete nums array. This is done so as to complete a circular traversal over the nums array. The first pass could make some wrong entries in the res array since it considers only the elements lying to the right of nums[i], without a circular traversal. But, these entries are corrected in the second pass.

Further, to ensure the correctness of the method, let’s look at the following cases.

Assume that nums[j] is the correct Next Greater Element for nums[i], such that i < j \leq stack[top]. Now, whenever we encounter nums[j], if nums[j] > nums\big[stack[top]\big], it would have already popped the previous stack[top] and j would have become the topmost element. On the other hand, if nums[j] < nums\big[stack[top]\big], it would have become the topmost element by being pushed above the previous stack[top]. In both the cases, if nums[j] > nums[i], it will be correctly determined to be the Next Greater Element.

The following example makes the procedure clear:

— animation —

As the animation above depicts, after the first pass, there are a number of wrong entries(marked as \text{-1}) in the res array, because only the elements lying to the corresponding right (non-circular) have been considered till now. But, after the second pass, the correct values are substituted.

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

Complexity Analysis

  • Time complexity : O(n). Only two traversals of the nums array are done. Further, at most \text{2n} elements are pushed and popped from the stack.
  • Space complexity : O(n). A stack of size n is used. res array of size n is used.
041

Leave a reply