Coding Interview PatternsNext Greater Element II
MediumMonotonic Stack

Next Greater Element II

Explanation & Solution

Practice Problem

Description

Given a circular integer array nums, return the next greater number for every element in the array.

The next greater number of a number x is the first number that is greater than x when traversing the array circularly. If no greater number exists, return -1 for that element.

Input:nums = [1,2,1]
0
1
1
2
2
1
Output:[2,-1,2]
0
2
1
-1
2
2

Explanation: The next greater number for 1 (index 0) is 2. There is no greater number for 2, so it returns -1. The next greater number for 1 (index 2) wraps around circularly to 2 at index 1.

Constraints

  • 1 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9

Approach

Monotonic Stack pattern

1. Initialize Result Array and Stack

  • Create a result array of length n, filled with -1 (default for elements with no greater element)
  • Create an empty stack that will store indices of elements waiting to find their next greater element

2. Iterate Twice Through the Array (Simulate Circular)

  • Loop from i = 0 to 2 * n - 1
  • Use i % n to get the actual index in the array
  • The second pass handles the circular wrap-around, allowing elements from the first pass to find greater elements that appear before them

3. Process the Stack

  • While the stack is not empty and nums[stack.top] is less than nums[i % n]:
  • Pop the index from the stack
  • Set result[popped] = nums[i % n] — this is the next greater element
  • This maintains a monotonic decreasing stack by value

4. Push Current Index (First Pass Only)

  • Only push the index onto the stack during the first pass (i < n)
  • During the second pass, we only resolve remaining elements on the stack without adding duplicates

5. Return the Result

  • After both passes, any indices still on the stack have no next greater element and remain -1
  • Return the result array

Key Insight

  • A monotonic stack efficiently finds the next greater element by maintaining elements in decreasing order. When a larger element is encountered, all smaller elements on the stack are resolved.
  • Iterating 2 * n times simulates the circular traversal without physically duplicating the array.
Time
O(n)each element is pushed and popped from the stack at most once
Space
O(n)for the stack and result array

Visualization

Input:
[1, 2, 1]
102112
—

No animation available

Left (L)Right (R)ConvergedDone
0 steps

Solution Code

Previous
Daily Temperatures
Next
Online Stock Span