Next Greater Element I
You get two arrays of distinct integers, nums1 and nums2, and every value of nums1 also appears in nums2. The next greater element of a value x is the first value to the right of x in nums2 that is larger than x, or -1 if no such value exists.
Return an array holding the next greater element of each value of nums1, in the order of nums1.
Function
- nums1integer-array
- the values to answer, all of them found in nums2
- nums2integer-array
- the array in which you look to the right of each value
- Returnsinteger-array
- the next greater element of each value of nums1, or -1, in the order of nums1
Constraints
1 ≤ nums1.length ≤ nums2.length ≤ 1040 ≤ nums1[i], nums2[i] ≤ 104- All values in
nums1are distinct, and all values innums2are distinct. - Every value of
nums1appears innums2.
Examples
- Input
- nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
- Output
- [8, -1, 6]
- Explanation
- After the 3 in
nums2come 8 and 2, and 8 is the first larger one. Only 2 follows the 8, so 8 gets -1. Right after 1 comes 6, already larger.
- Input
- nums1 = [5, 2]nums2 = [2, 9, 5, 4]
- Output
- [-1, 9]
- Explanation
- Only 4 follows the 5, and it is smaller, so 5 gets -1. Right after 2 comes 9. The answers follow the order of
nums1.
- Input
- nums1 = [10, 0]nums2 = [0, 10, 11]
- Output
- [11, 10]
- Explanation
- The first value after 10 is 11. The first value after 0 is 10, which is larger, so 0 gets 10 even though 11 comes later and is larger still.
Follow-up
For every position of nums2, can you return how many steps to the right its next greater element sits, with the same single pass?
Hints
Open them one at a time. Each one gives away a little more.
Scanning to the right of each value of
nums1can cost up to 10^4 steps per value. The answers depend only onnums2. Could you work out the next greater element of every value ofnums2in one pass, and then look up the values ofnums1?Walk
nums2from left to right and keep the values that have not met a larger value yet. When a new value arrives, it is the answer for every waiting value smaller than it. The waiting values always form a decreasing sequence, so the smaller ones sit on top of a stack.For each value of
nums2: while the top of the stack is smaller than it, pop the top and record the current value as its answer in a hash map. Then push the current value. At the end, answer each value ofnums1from the map, with -1 for a value that was never popped.
Solution
Scanning right from every value of nums1 repeats work, and the answers depend only on nums2. One walk with a monotonic stack finds the next greater element of every value of nums2 at once. A hash map keeps them, and nums1 is answered by lookup.
Find each value and scan right
Correct, but does not finish on the largest tests
Intuition
For each value x of nums1, find x in nums2 and scan right to the first larger value, or -1 at the end. The scan visits the values to the right of x in order, so the first larger one it meets is the answer.
If nums2 is decreasing, every scan walks to the end: up to m × n steps, 10^8 when both arrays hold 10^4 values.
Algorithm
- Loop over each value
xofnums1. - Find the index
jwherenums2[j]equalsx. - Scan
nums2fromj+1and stop at the first value larger thanx. - Append that value, or -1 if the scan reached the end.
- Return the collected answers.
def nextGreaterElement(nums1, nums2):
result = []
for x in nums1:
j = 0
while nums2[j] != x:
j += 1
answer = -1
for k in range(j + 1, len(nums2)):
if nums2[k] > x:
answer = nums2[k]
break
result.append(answer)
return resultMonotonic stack and a hash map
Intuition
Walk nums2 once and let each new value answer the earlier values it beats. Keep the values still waiting for an answer on a stack. When a value arrives, pop every smaller value from the top and map it to the new value, the first larger one to its right. Then push the new value.
The stack decreases from bottom to top, because a value is pushed only after every smaller value above it was popped, so you only ever look at the top. A value leaves the moment the first larger value appears, so its answer is the first larger value, not the largest.
On [1, 6, 3, 8, 2], 6 pops 1, then 8 pops 3 and 6, and 8 and 2 end with no answer. Each value is pushed once and popped at most once, so with the m lookups the time is O(n + m).
Algorithm
- Create an empty map and an empty stack.
- For each value of
nums2, pop every smaller value from the top of the stack and map it to the current value. - Push the current value onto the stack.
- For each value of
nums1, return its mapped answer, or -1 if it has none.
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = [] # values still waiting for a greater one, decreasing from bottom to top
for value in nums2:
# value is the first greater value to the right of every smaller value on the stack.
while stack and stack[-1] < value:
next_greater[stack.pop()] = value
stack.append(value)
# Whatever is still on the stack has no greater value to its right.
return [next_greater.get(x, -1) for x in nums1]
Pitfalls and edge cases
- Recording the largest value to the right instead of the first larger one. In
nums2 = [3, 5, 1, 2, 4, 9, 0]the answer for 1 is 2, not 9. - Returning answers in the order of
nums2. The result has one entry per value ofnums1, in its order:[-1, 9]in the second example. - Reading
nums2at the index a value has innums1. In the first example 3 sits at index 0 ofnums1but at index 2 ofnums2. - Forgetting the values left on the stack. Their answer is -1, and a map lookup with no default fails for them.
Frequently asked questions4
What is the time complexity of Next Greater Element I?
The monotonic stack solution runs in O(n + m) time, where n is the length of nums2 and m the length of nums1, and uses O(n) space for the map and the stack. Scanning right from each value takes O(n·m) time.
What is a monotonic stack?
A stack whose values stay sorted from bottom to top. Before you push a value, you pop everything that would break the order, and each pop is where an answer is found. It solves next greater, next smaller and similar questions in linear time.
Why does Next Greater Element I need a hash map?
The stack walk produces answers keyed by the values of nums2, in the order they leave the stack. The output follows nums1, where the same values sit at other positions. All values are distinct, so a map from value to answer connects the two arrays with one constant time lookup each.
What changes if nums2 is circular?
The search for a larger value may then continue from the start of the array. Run the same stack walk twice, with index i % n for i from 0 to 2n-1, and push values only in the first round. Values still on the stack after both rounds have no larger value anywhere, so their answer is -1.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def nextGreaterElement(nums1, nums2):
# Write code hereTest #1
Test #2
Test #3
Arguments
nums1 = [3, 8, 1] nums2 = [1, 6, 3, 8, 2]
Expected Output
[8, -1, 6]