MediumArrayStackMonotonic StackUpdated Sep 2026

503. Next Greater Element II

Asked at Microsoft

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You are given an integer array nums that is circular. This means the element after the last one is the first one again. For every position in the array, find its next greater element.

The next greater element of nums[i] is the first value you meet when you walk forward from i (wrapping around the end back to the start) that is strictly greater than nums[i]. If you can never find such a value, the answer for that position is -1.

Return an array result of the same length, where result[i] is the next greater element of nums[i]. You may look at each element more than once because the search can wrap around, but each position still gets exactly one answer.

The array is a circle

numswrap around121012The last 1 looks forward, wraps past index 0, andfinds 2 at index 1.
After the last element we jump back to the first, so a value near the end can find its answer at the front.

Constraints

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

Examples

Example 1
Inputnums = [1,2,1]
Output[2,-1,2]
WhyFor index 0 (value 1), the next value is 2, which is greater, so the answer is 2. For index 1 (value 2), nothing in the whole circle is greater than 2, so the answer is -1. For index 2 (value 1), we wrap around to index 0 (value 1, not greater) and then index 1 (value 2, greater), so the answer is 2
Example 2
Inputnums = [1,2,3,4,3]
Output[2,3,4,-1,4]
WhyEach of the first three values finds the next bigger value right after it: 1→2, 2→3, 3→4. The value 4 at index 3 has no greater value anywhere, so it gets -1. The last value 3 wraps around and finds 4 at index 3, so it gets 4.

Asked At

1 companies
CompanyDifficulty
MicrosoftMediumView all Microsoft questions →

How to Think About It

1

Key insight: simulate the circular array by iterating through nums twice (or using index modulo n). This lets you find the next greater element wrapping around from the end to the beginning.

2

Monotonic stack: maintain a stack of indices whose next greater element hasn't been found yet. The stack stores indices in decreasing order of their values. When you encounter a value greater than the stack top, you've found the next greater element for all smaller values.

3

The algorithm: iterate i from 0 to 2n-1. Use idx = i % n to access the array circularly. While the stack is not empty and nums[stack[-1]] < nums[idx], pop the stack and set result[popped] = nums[idx]. If i < n, push i onto the stack.

4

Why iterate twice: the first pass finds next greater elements within the non-wrapped portion. The second pass handles elements near the end that might wrap around to find their next greater at the beginning. Each element is pushed and popped at most once.

5

Time: O(n) since each element is pushed and popped at most once across both passes. Space: O(n) for the stack and result array.

Optimal Approach

Monotonic stack with double iteration:

  1. Initialize result = [-1] * n and empty stack.
  2. For i from 0 to 2n - 1:
    a. idx = i % n
    b. While stack is not empty and nums[stack[-1]] < nums[idx]:
    • popped = stack.pop()
    • result[popped] = nums[idx]
      c. If i < n, push i onto stack.
  3. Return result.

Walkthrough: nums = [1, 2, 3, 4, 3].

  • i=0: push 0. Stack=[0].
  • i=1: nums[0]=1 < 2. Pop 0, result[0]=2. Push 1. Stack=[1].
  • i=2: nums[1]=2 < 3. Pop 1, result[1]=3. Push 2. Stack=[2].
  • i=3: nums[2]=3 < 4. Pop 2, result[2]=4. Push 3. Stack=[3].
  • i=4: nums[3]=4 > 3. Push 4. Stack=[3,4].
  • i=5, idx=0: nums[0]=1 < 3? No. No pop.
  • i=6, idx=1: nums[1]=2 < 3? No. No pop.
  • i=7, idx=2: nums[2]=3 < 3? No. No pop.
  • i=8, idx=3: nums[3]=4 > 3. Pop 4, result[4]=-1. Pop 3, result[3]=-1.
    Result: [2, 3, 4, -1, -1].

Time: O(n). Space: O(n).

Monotonic stack over two passes

stack (indices)0← topPass 1, i=0: nothing to compare yet, so push index 0.stack (indices)12← topPass 1, i=1: value 2 pops index 0 (result[0]=2), thenindex 1 is pushed; i=2 pushes index 2.stack (indices)1← topPass 2, i=4 (idx=1): value 2 pops index 2, soresult[2]=2. Index 1 stays because 2 is not less than2.while stack and nums[top] < nums[idx]: result[pop()] = nums[idx]push idx only when i < n
We scan the array twice using index modulo n, and a decreasing stack holds positions still waiting for their answer.
ComplexityTime O(n)Space O(n)Each index is pushed and popped from the stack at most once across the two passes, and the result array plus stack use O(n) extra space.

What Trips People Up in Real Interviews

1

Not handling the circular nature. If you only iterate once, elements at the end can't find next greater elements at the beginning. The double-iteration trick (or modulo indexing) solves this.

2

Using a stack of values instead of indices. You need indices to update the result array at the correct positions. Store indices, compare values using nums[index].

3

Pushing elements during the second pass. Only push during i < n (first pass). The second pass only pops to find next greater for remaining stack elements. Pushing in the second pass wastes space.

4

Forgetting to initialize the result array with -1. If no next greater element is found, the result should be -1. Initialize result = [-1] * n before starting.

5

Confusing strict greater with greater-or-equal. The problem says "greater", meaning strictly greater. nums[stack[-1]] < nums[idx] uses strict less-than. If equal values exist, don't pop.

Solution Code

O(n) time
def nextGreaterElements(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(2 * n):
        idx = i % n
        while stack and nums[stack[-1]] < nums[idx]:
            result[stack.pop()] = nums[idx]
        if i < n:
            stack.append(i)
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Next Greater Element II problem?

Given a circular integer array nums, return the next greater element for each element. The next greater element is the first element that is greater and appears after it (circularly). If no greater element exists, return -1. A monotonic stack handles this in `O(n)` time.

How do you solve Next Greater Element II?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Next Greater Element II?

Next Greater Element II is asked at Microsoft. It is a medium difficulty problem.

What are common mistakes on Next Greater Element II?
  • Not handling the circular nature. If you only iterate once, elements at the end can't find next greater elements at the beginning. The double-iteration trick (or modulo indexing) solves this.
  • Using a stack of values instead of indices. You need indices to update the result array at the correct positions. Store indices, compare values using `nums[index]`.
  • Pushing elements during the second pass. Only push during i < n (first pass). The second pass only pops to find next greater for remaining stack elements. Pushing in the second pass wastes space.
  • Forgetting to initialize the result array with -1. If no next greater element is found, the result should be -1. Initialize result = [-1] * n before starting.
  • Confusing strict greater with greater-or-equal. The problem says "greater", meaning strictly greater. `nums[stack[-1]] < nums[idx]` uses strict less-than. If equal values exist, don't pop.