Pattern visualizer
Next Greater Element II
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. 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]..
Monotonic stack, walked twice for the wrap-around
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