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.

Details

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].

Problem:Next Greater Element IEasy

Pattern:Monotonic Stack

Stack

step 1 / 8

[0]

[1]

[2]

[3]

Step 1: Start iterating nums2. i=0, num=1. Stack empty, push 1. Stack: [1]. Current element 1 has no next greater yet.

i=0· arr[0] = 1

Pseudocode

1FUNCTION nextGreaterElement(nums1, nums2):
2  make an empty lookup table (value -> its next greater value)
3  make an empty stack
4  FOR each num in nums2:
5    WHILE the stack is not empty and num > the top of the stack:
6      pop the top into prev
7      store prev -> num in the table
8    push num onto the stack
9  FOR each value in nums1:
10    replace it with the table's value for it, or -1 if absent
11  RETURN nums1

← / → step · space play · Home restart

Every step in words

Show all 8 steps

Step 1: Start iterating nums2. i=0, num=1. Stack empty, push 1. Stack: [1]. Current element 1 has no next greater yet.
Step 2: i=1, num=3. 3 > stack[-1]=1, so pop 1 and set nextGreater[1]=3. Push 3. Stack: [3]. Element 1 now has next greater 3.
Step 3: i=2, num=4. 4 > stack[-1]=3, so pop 3 and set nextGreater[3]=4. Push 4. Stack: [4]. Element 3 now has next greater 4.
Step 4: i=3, num=2. 2 > stack[-1]=4? No (2 < 4). Push 2. Stack: [4, 2]. Both 4 and 2 will have no next greater after this pass.
Step 5: Finished iterating nums2. Stack: [4, 2]. Remaining elements 4 and 2 have no next greater to the right. Map so far: nextGreater = {1: 3, 3: 4}. Both 4 and 2 will map to -1.
Look up nums1 values now. nums1[0]=4. nextGreater.get(4, -1) = -1 (4 had no greater in nums2). Result so far: -1.
nums1[1]=1. nextGreater.get(1, -1) = 3. Element 1's next greater in nums2 is 3. Result so far: 3.
nums1[2]=2. nextGreater.get(2, -1) = -1 (2 had no greater in nums2). Final result: [-1, 3, -1].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Next Greater Element I in the editor All Stack problems Back to roadmap