Problem Description

You are given a circular integer array nums. In a circular array, the element after the last element nums[nums.length - 1] connects back to the first element nums[0].

For each element in the array, you need to find its next greater number. The next greater number for an element x is the first number that is greater than x when you traverse the array in order. Since the array is circular, if you reach the end of the array without finding a greater number, you can continue searching from the beginning of the array.

If no greater number exists for an element (even after searching the entire circular array), return -1 for that element.

Example:

• If nums = [1, 2, 1], the output would be [2, -1, 2]
  • For nums[0] = 1: moving forward, we find 2 which is greater than 1
  • For nums[1] = 2: searching circularly through the entire array, no element is greater than 2
  • For nums[2] = 1: moving forward circularly to the beginning, we find 2 which is greater than 1

The solution uses a monotonic stack approach. By traversing the array twice (to handle the circular nature) from right to left, we maintain a stack that keeps track of potential "next greater" elements. For each position, we pop elements from the stack that are not greater than the current element, then the top of the stack (if it exists) becomes the next greater element for that position. This approach efficiently finds the next greater element for each position in O(n) time complexity.

Intuition

The key insight is to think about what information we need when we're at each position. For any element, we want to know: "What's the first element greater than me if I look to my right?"

A naive approach would be to check every element to the right for each position, but this would be inefficient. Instead, we can use a stack to keep track of "candidate" greater elements as we traverse the array.

Why traverse from right to left? When we process an element from right to left, we already know all the elements that come after it. This allows us to maintain a stack of potential "next greater" elements. The stack naturally maintains elements in a way where smaller elements that can't be the answer for anyone get removed.

Here's the clever part: when we're at position i, we pop all elements from the stack that are <= nums[i]. Why? Because if an element in the stack is smaller than or equal to nums[i], it can never be the "next greater element" for any element to the left of i. The current element nums[i] would be a better candidate since it's both closer and at least as large.

After popping, the top of the stack (if it exists) is the next greater element for position i. Then we push nums[i] onto the stack as it might be the answer for elements to its left.

To handle the circular nature, we simply traverse the array twice. By doing (n * 2 - 1) iterations and using modulo (i % n), we simulate going around the circle once. This ensures that even the last elements in the array get a chance to "see" the elements at the beginning as potential next greater elements.

The stack maintains a monotonic decreasing order from bottom to top, which is why this technique is called a "monotonic stack."

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The solution uses a monotonic stack to efficiently find the next greater element for each position in the circular array.

Implementation Steps:

1. Initialize the result array and stack:

   • Create an array ans of size n initialized with -1 (default value when no greater element exists)
   • Create an empty stack stk to maintain potential next greater elements

2. Traverse the array from right to left, twice:

   • Start from index n * 2 - 1 and go down to 0
   • For each iteration, calculate the actual array index using i %= n to handle the circular nature

3. Maintain the monotonic stack:

   • While the stack is not empty and the top element is <= nums[i]:
     • Pop elements from the stack
     • These popped elements cannot be the next greater element for any future positions since nums[i] is both closer and at least as large

4. Record the next greater element:

   • After popping, if the stack is not empty:
     • The top element of the stack is the next greater element for position i
     • Set ans[i] = stk[-1]

5. Add current element to stack:

   • Push nums[i] onto the stack
   • This element might be the next greater element for positions to its left

Why this works:

• By traversing from right to left, we ensure that when processing position i, the stack contains all valid candidates from positions to the right of i
• The stack maintains elements in decreasing order (from bottom to top), so the first element greater than nums[i] will be at the top after popping smaller elements
• Traversing twice (using n * 2 - 1 iterations) simulates the circular array - elements at the beginning of the array can be the next greater element for elements at the end

Time Complexity: O(n) - Each element is pushed and popped from the stack at most twice
Space Complexity: O(n) - The stack can contain at most n elements

Example Walkthrough

Let's walk through the solution with nums = [2, 1, 3, 1]:

Initial Setup:

• n = 4
• ans = [-1, -1, -1, -1]
• stk = []
• We'll iterate from i = 7 down to 0 (processing 8 positions for circular behavior)

Iteration Details:

Final Result: [3, 3, -1, 2]

Verification:

• nums[0] = 2: Next greater is 3 (at index 2) ✓
• nums[1] = 1: Next greater is 3 (at index 2) ✓
• nums[2] = 3: No element greater than 3 in the circular array ✓
• nums[3] = 1: Next greater is 2 (circularly at index 0) ✓

The key insight demonstrated here is how the stack maintains potential candidates. When we process an element, we remove all smaller elements from the stack (they can't be the answer for anyone to the left), and the remaining top element (if any) is our answer. The double traversal ensures we handle the circular nature correctly.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through 2n elements (from 2n-1 to 0). For each element, it performs operations with the stack. While there's a nested while loop that pops elements from the stack, each element can be pushed and popped from the stack at most once throughout the entire execution. Therefore, the total number of operations across all iterations is bounded by O(n) for the loop iterations plus O(n) for all stack operations combined, resulting in O(n) overall time complexity.

Space Complexity: O(n)

The algorithm uses two data structures that scale with input size:

• The ans array of size n to store the results: O(n)
• The stk stack which, in the worst case, can contain all n unique elements: O(n)

Therefore, the total space complexity is O(n) + O(n) = O(n), where n is the length of the array nums.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle the Circular Nature Properly

A common mistake is only traversing the array once instead of twice, which fails to find next greater elements that wrap around from the beginning of the array.

Incorrect approach:

# This only goes through the array once - misses circular connections
for i in range(n - 1, -1, -1):
    # Process logic here

Correct approach:

# Traverse twice to handle circular nature
for i in range(n * 2 - 1, -1, -1):
    index = i % n  # Use modulo to get actual array index

2. Using Wrong Comparison in Stack Maintenance

Another pitfall is using the wrong comparison operator when popping from the stack. Using < instead of <= will cause duplicate values to be incorrectly handled.

Incorrect:

# This keeps equal elements in stack - wrong for "next greater"
while stack and stack[-1] < nums[index]:
    stack.pop()

Correct:

# Pop elements that are less than OR EQUAL to current
while stack and stack[-1] <= nums[index]:
    stack.pop()

3. Updating Result Array in the Wrong Loop Iteration

Some implementations mistakenly try to update the result array during both passes through the circular array, leading to incorrect overwrites.

Solution: Only update result[index] when i < n (first pass through), or simply let the modulo operation handle it naturally as shown in the correct solution. The key is ensuring each position's result is set exactly once with the correct next greater element.

4. Stack Index vs. Stack Value Confusion

Sometimes developers push indices onto the stack instead of values, or vice versa. The solution should be consistent about what the stack contains.

For this problem: The stack should contain values (not indices) since we need to compare actual numbers to find the next greater element.