Next Greater Element II
Asked at Microsoft
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Microsoft | Medium | View all Microsoft questions → |
How to Think About It
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.
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.
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.
Visual walkthrough: nums = [1, 2, 1].
- i=0, idx=0,
nums[0]=1. Stack empty. Push 0. Stack=[0]. - i=1, idx=1,
nums[1]=2.nums[0]=1 < 2. Pop 0,result[0]=2. Stack empty. Push 1. Stack=[1]. - i=2, idx=2,
nums[2]=1.nums[1]=2 > 1. Push 2. Stack=[1,2]. - i=3, idx=0,
nums[0]=1.nums[2]=1 < 1? No (equal, not strictly greater). Push? No, i >= n, don't push. - i=4, idx=1,
nums[1]=2.nums[2]=1 < 2. Pop 2,result[2]=2.nums[1]=2 not < 2. Stop. - i=5, idx=2,
nums[2]=1.nums[1]=2 > 1. Pop 1,result[1]=-1 (no more elements).
Result: [2, -1, 2].
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.
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:
- Initialize
result = [-1] * nand empty stack. - For i from 0 to 2n - 1:
a.idx = i % n
b. While stack is not empty andnums[stack[-1]] < nums[idx]:- popped = stack.pop()
result[popped] = nums[idx]
c. If i < n, push i onto stack.
- 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).
What Trips People Up in Real Interviews
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.
Solution Code
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 resultFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.