Next Greater Element I

Easy#496

You get two arrays of distinct numbers, and every number of nums1 is also somewhere in nums2. For each number of nums1, find it in nums2 and take the first number to its right that is greater; if there is none, the answer is -1. Our example: nums1 = [4, 7, 2], nums2 = [4, 1, 3, 7, 2, 5] gives [7, -1, 5].

496 Next Greater Element IWalkthrough · 1×

Example: nums1 = [4, 7, 2], nums2 = [4, 1, 3, 7, 2, 5]. One pass over nums2 fills greater, drawn under each number; the stack keeps the numbers still waiting. Then each number of nums1 is one lookup.

041123374255nums2greaterstack—nums1472answer
not reachedcurrent numberwaiting on the stacktop being checkednext greater found

An empty map: number → the next greater number after it in nums2

01/36
restart · back · play · step
Speed
1function nextGreaterElement(nums1, nums2):
2 greater = empty map // number → next greater
3 stack = empty stack
4 for x in nums2:
5 while stack not empty and x > top of stack:
6 greater[pop from stack] = x
7 push x onto stack
8 answer = empty list
9 for y in nums1:
10 if y in greater: append greater[y] to answer
11 else: append -1 to answer
12 return answer
state
greater
{}
stack
–
x
–
y
–
answer
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. A number waits on the stack until the first greater number comes; that one pops it, so it is exactly its next greater. The numbers on the stack only fall towards the top, so a greater number pops them from the top down and the loop stops at the first one it does not beat.
  2. All numbers are distinct, so the number itself can be the key of the map and the stack can hold numbers, not indices.
  3. A number left on the stack at the end has nothing greater after it. It never gets into the map, so its lookup gives -1.

Complexity

Time O(n + m) for n numbers in nums2 and m in nums1: each number of nums2 is pushed once and popped at most once, and each lookup is O(1). Memory O(n) for the map and the stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.