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 one larger than 3. Only 2 follows the 8, so 8 gets -1. The value right after 1 is 6, which is already larger.
- Input
- nums1 = [5, 2]nums2 = [2, 9, 5, 4]
- Output
- [-1, 9]
- Explanation
- Only 4 follows the 5, and 4 is smaller, so 5 gets -1. The value right after 2 is 9. The answers follow the order of
nums1, not the order ofnums2.
- 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.
+14 hidden tests on Submit
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
For one value the answer is a scan to its right, but a scan for every value of nums1 costs up to nums1.length × nums2.length steps. The answers depend only on nums2, so you can find the next greater element of every value of nums2 at once with a monotonic stack, keep them in a hash map, and answer nums1 by lookup.
Find each value and scan right
Correct, but does not finish on the largest tests
Intuition
Do what the definition says. For a value x of nums1, walk nums2 until you reach x. Then keep walking and stop at the first value larger than x. If you reach the end without one, the answer is -1.
This is correct because the scan visits the values to the right of x in order, so the first larger value it meets is the first larger value there is.
It is slow when the answers are far away or missing. If nums2 is decreasing, no scan ever finds a larger value, and every value of nums1 walks to the end. With m values in nums1 and n in nums2 that is up to m × n steps: 10^8 when both arrays hold 10^4 values. Every scan also covers ground that earlier scans already walked.
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
Turn the question around. Instead of asking, for each value, what comes after it, walk nums2 once and let each new value answer the earlier values it beats. Keep the values that have no answer yet on a stack. When a value arrives, pop every smaller value from the top: the new value is the first larger one to their right, so it is their answer. Then push the new value, which is still waiting for its own answer.
Walk through nums2 = [1, 6, 3, 8, 2]. Push 1. Then 6 arrives and beats 1, so 1 maps to 6; push 6. Then 3 arrives, does not beat 6, and is pushed on top: the stack is [6, 3]. Then 8 pops 3 and 6, so both map to 8; push 8. Then 2 is pushed. The stack ends as [8, 2], and those two have no answer. For nums1 = [3, 8, 1] the map gives [8, -1, 6].
The stack is always decreasing from bottom to top, because a value is pushed only after every smaller value above it was popped. That is why you only ever need to look at the top. A value leaves the stack the moment the first larger value appears, so the answer you record is the first one, not the largest one.
Each value of nums2 is pushed once and popped at most once, so the inner loop does at most n pops in total across the whole walk. With the m lookups the time is O(n + m). The map is what links the two arrays: the values are distinct, so a value is a safe key, even though it sits at different positions in nums1 and nums2. The C and R solutions use an array of 10^4+1 slots indexed by value as the map, which works because no value exceeds 10^4.
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
The stack itself is short code; the mistakes are in what you record and where you look.
- 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 the answers in the order of
nums2, or for every value ofnums2. The result has one entry per value ofnums1, in its order. - Returning an index instead of a value. The problem asks for the larger value itself.
- Reading
nums2at the index a value has innums1. The same value sits at different positions in the two arrays; find it by value, which is what the map is for. - Forgetting the values left on the stack at the end. They never met a larger value, so their answer is -1; a map lookup with no default fails or returns nothing for them.
- Looking to the left, or wrapping around to the start of
nums2. Only values to the right count, and the array does not wrap.
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. Each value of nums2 is pushed and popped at most once, and each value of nums1 is one map lookup. The map and the stack use O(n) space. Scanning right from each value takes O(n·m) time.
What is a monotonic stack?
It is a stack whose values stay sorted from bottom to top, here decreasing. Before you push a new value, you pop everything that would break the order, and those pops are where the work happens: each popped value has found its first larger value to the right. 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 in the order values leave the stack, keyed by the values of nums2. The output must follow the order of nums1, where the same values sit at other positions. Since all values are distinct, a map from value to answer connects the two arrays with a constant time lookup per value.
What changes if nums2 is circular?
Then the search for a larger value may continue from the start of the array. Run the same stack walk over the array twice, using index i % n for i from 0 to 2n-1, and push values only during the first round. Values that are 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.
Python
def nextGreaterElement(nums1, nums2):
# Write code hereCase 1
Case 2
Case 3
Input
nums1 = [3, 8, 1] nums2 = [1, 6, 3, 8, 2]
Expected
[8, -1, 6]