Next Greater Element II | Leetcode 503 | Imaginary List Optimal Solution

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.

Here’s the [Problem Link] to begin with.

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

Optimal Approach: Monotonic Stack for Circular Arrays

Intuition

• In a non-circular Next Greater Element problem, you process elements from right to left using a stack and can stop once you reach the beginning.
• In the circular case, an element’s NGE might only appear after the end, so you must symbolically “loop” through the array twice.
• This is achieved by iterating from 2*n – 1 down to 0, using i % n so the second “pass” is seamless.

Detailed Approach

• Prepare a result array (size n), all -1.
• Traverse from index 2*n-1 to 0 (effectively simulating two passes).
• At each index i:
  • While stack isn’t empty and stack’s top is ≤ current value, pop from stack.
  • If within the first pass (i < n), set the result: if stack not empty, NGE is stack top; else, -1.
  • Push current value onto the stack for use in subsequent NGE lookups.

Code

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [-1] * n    # Initialize results with -1
        stack = []           # Stack for potential NGEs

        # Loop twice to simulate circular array
        for i in range(2 * n - 1, -1, -1):
            # Maintain decreasing stack
            while stack and stack[-1] <= nums[i % n]:
                stack.pop()
            # Only set result during the first 'real' pass
            if i < n:
                if stack:
                    result[i] = stack[-1]
            # Push current value for next iteration checks
            stack.append(nums[i % n])
        return result

Code Explanation

• Processing from right to left and looping twice lets every number have access to all elements on its right, even those past the end.
• Stack: Keeps potential “Next Greater Elements”, always in descending order.
• For each index:
  • Pop smaller (or equal) elements, they cannot be NGE for anyone to their left.
  • For the first n elements, update result if stack isn’t empty.
  • Push current value for future queries.

Dry Run Example

nums = [1, 2, 1]

• i = 5 (nums = 1): stack empty; push 1.
• i = 4 (nums = 2): pop 1 (since 1 < 2); stack empty; push 2.
• i = 3 (nums = 1): stack top 2 > 1; NGE=2; push 1.
• Now first pass:
• i = 2 (nums=1): stack top 2 > 1; result=2; push 1.
• i = 1 (nums=2): pop 1; stack top 2 = 2; pop 2; stack empty; result=-1; push 2.
• i = 0 (nums=1): stack top 2 > 1; result=2; done.

Result: [2, -1, 2]

Time and Space Complexity

• Time: O(n), where n = len(nums). Every element is pushed/popped at most twice (over two passes).
• Space: O(n) for the result array and the stack.

Simplified

• Monotonic stack, classic method for all NGE type problems.
• “Looping” via i % n elegantly handles circular logic.

Summary Table

Conclusion

The Next Greater Element II (circular variant) is the perfect interview test of your stack and array mastery. Practice with several input types (all equal, strictly decreasing, etc.), and always loop twice for circular logic using the modulo trick!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.