The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2] Output: [-1,3,-1] Explanation: The next greater element for each value of nums1 is as follows: - 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1. - 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3. - 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4] Output: [3,-1] Explanation: The next greater element for each value of nums1 is as follows: - 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3. - 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.
Constraints:
1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 10^4nums1 and nums2 are unique.nums1 also appear in nums2.
Follow up: Could you find an O(nums1.length + nums2.length) solution?
The description was taken from https://leetcode.com/problems/next-greater-element-i/.
#O(N) Time, O(N) Space
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
output, stack, seen = [], [], {}
for num in nums2:
if stack and num < stack[-1]:
stack.append(num)
continue
while stack and num > stack[-1]:
last_num = stack.pop()
seen[last_num] = num
stack.append(num)
for num in nums1:
if num in seen:
output.append(seen[num])
else:
output.append(-1)
return output
The problem asks us to find the next greater value for each number if it exists.
When we see a requirement like that, a monotonic stack is a good approach.
We can go through the second array and for each value, we will push them onto a stack if they are less than the top value. If each value on the stack is decreasing, we won't have an answer for what the next greater value is until we get to a greater value than what is on top of the stack. At that point, we can continuously pop any value that is less and answer the question for them with that current value.
Let's start by initializing our output, our stack, and a hashmap to map the greater value for each number we find.
output, stack, seen = [], [], {}
Then, we will traverse the second array.
For each number, if that number is less than the top value on the stack, then we can't answer what the next greater value is for any number in the stack at this point.
We will just append the current number and continue.
for num in nums2:
if stack and num < stack[-1]:
stack.append(num)
continue
Otherwise, we have a number with a greater value than the top of the stack, so we will begin popping off any value less than the current number and writing in our hashmap that the greater value for these elements is the current number.
while stack and num > stack[-1]:
last_num = stack.pop()
seen[last_num] = num
Once we have finished popping off any lesser number from the stack, we will append the current number.
stack.append(num)
When we finish traversing the second array, any number with a greater value will have the number mapped to it within the seen hashmap.
For each number in the first array, if that number has a greater value, we will append the greater value to the output.
for num in nums1:
if num in seen:
output.append(seen[num])
Otherwise, we will append a negative one.
else:
output.append(-1)
Once we have each greater value in the output, we will return it.
return output