Next Greater Element II
Monotonic stack, walked twice for the wrap-around
Next Greater Element I already shows the trick: hold a stack of elements that have not yet met anything bigger, keep it decreasing, and let each arriving number settle everyone smaller than it in one go. Circularity adds exactly one wrinkle — an element near the end may be answered by an element near the start, which a single left-to-right pass never shows it. The fix is not a second data structure but a second lap: run the same loop for 2n iterations, indexing with i mod n. The second lap only pops, never pushes, because every index is already on the stack from lap one and pushing again would let an element answer itself. Anything still on the stack after both laps has now been compared against the whole array, so it is a maximum and its answer is -1.
Details
Animated on: nums = [3, 7, 8, 6, 1, 5, 2] — the array is circular, so searching past the last index continues at index 0. For each element report the first strictly greater element going right. Answer: [7, 8, -1, 7, 5, 7, 3].
Problem:Next Greater Element IIMedium
Pattern:Monotonic Stack
Monotonic stack, walked twice for the wrap-around
step 1 / 12
nums=[3, 7, 8, 6, 1, 5, 2] is CIRCULAR, so index 6 may still find its answer by wrapping round to index 0. Keep a stack of indices whose answer is still unknown; their values always run downhill, so the first bigger number to arrive settles all of them at once.
1FUNCTION nextGreaterElements(nums):2 n <- LENGTH(nums)3 ans <- ARRAY OF n COPIES OF -14 stack <- EMPTY5 FOR i <- 0 TO 2 * n - 1:6 v <- nums[i MOD n]7 WHILE stack NOT EMPTY AND nums[TOP(stack)] < v:8 j <- POP stack9 ans[j] <- v10 IF i < n:11 PUSH i MOD n ONTO stack12 RETURN ans
← / → step · space play · Home restart
Every step in words
Show all 12 steps
- nums=[3, 7, 8, 6, 1, 5, 2] is CIRCULAR, so index 6 may still find its answer by wrapping round to index 0. Keep a stack of indices whose answer is still unknown; their values always run downhill, so the first bigger number to arrive settles all of them at once.
- nums[0]=3 is not bigger than anything waiting (the stack is empty), so it settles nobody and joins the queue itself. Waiting: [3].
- nums[1]=7 is bigger than nums[0]=3, and it is the FIRST bigger number it has seen, so ans[0]=7. 7 has no answer of its own yet, so it waits in the queue too. Waiting: [7].
- nums[2]=8 is bigger than nums[1]=7, and it is the FIRST bigger number it has seen, so ans[1]=8. 8 has no answer of its own yet, so it waits in the queue too. Waiting: [8].
- nums[3]=6 is not bigger than the 8 on top of the stack, so it settles nobody and joins the queue itself. Waiting: [8, 6].
- nums[4]=1 is not bigger than the 6 on top of the stack, so it settles nobody and joins the queue itself. Waiting: [8, 6, 1].
- nums[5]=5 is bigger than nums[4]=1, and it is the FIRST bigger number it has seen, so ans[4]=5. 5 has no answer of its own yet, so it waits in the queue too. Waiting: [8, 6, 5].
- nums[6]=2 is not bigger than the 5 on top of the stack, so it settles nobody and joins the queue itself. Waiting: [8, 6, 5, 2].
- First lap done, and 4 indices (8, 6, 5, 2) never met a bigger number going right. Walk the array a SECOND time so they can see what wraps around — this lap only pops, it never pushes, or an element could end up answering itself.
- Second lap, back at nums[0]=3. It is bigger than nums[6]=2, which the first lap could not answer because nothing to its right beat it — wrapping is the only way to reach index 0 from there: ans[6]=3. Waiting: [8, 6, 5].
- Second lap, back at nums[1]=7. It is bigger than nums[5]=5 and nums[3]=6, which the first lap could not answer because nothing to their right beat them — wrapping is the only way to reach index 1 from there: ans[5]=7, ans[3]=7. Waiting: [8].
- Both laps done. nums[2]=8 is still on the stack having now been compared against every other element, so nothing beats it and ans[2]=-1. Answer: [7, 8, -1, 7, 5, 7, 3].
Now solve it yourself
Watching is the first half. The second is writing it without the animation.