Pattern visualizer
Next Greater Element I
The key insight: instead of scanning ahead from every element to find its next greater value (O(n^2)), keep a stack of elements that are still 'waiting' for something bigger. The moment a bigger number arrives, it instantly resolves every smaller element still waiting below it on the stack — since it's the first bigger number they've seen — so each element is pushed and popped exactly once while building a value-to-next-greater map over nums2. Whatever's left on the stack at the end never found one, so it maps to -1; then each nums1 value is just a lookup in that map. Animated on: nums1=[4,1,2], nums2=[1,3,4,2]; monotonic stack over nums2 builds value-to-next-greater map, then nums1 looks each value up. Answer: [-1,3,-1]..
Stack
Step 1: Start iterating nums2. i=0, num=1. Stack empty, push 1. Stack: [1]. Current element 1 has no next greater yet.
1FUNCTION nextGreaterElement(nums1, nums2):2 make an empty lookup table (value -> its next greater value)3 make an empty stack4 FOR each num in nums2:5 WHILE the stack is not empty and num > the top of the stack:6 pop the top into prev7 store prev -> num in the table8 push num onto the stack9 FOR each value in nums1:10 replace it with the table's value for it, or -1 if absent11 RETURN nums1
← / → step · space play · Home restart