0% completed
Problem Statement
Given two integer arrays nums1
and nums2
, return an array answer
such that answer[i]
is the next greater number for every nums1[i]
in nums2
.
The next greater element for an element x
is the first element to the right of x
that is greater than x
. If there is no greater number, output -1
for that number.
The numbers in nums1
are all present in nums2
.
Examples
-
- Input:
nums1 = [4,2,6]
,nums2 = [6,2,4,5,3,7]
- Output:
[5,4,7]
- Explanation: The next greater number for 4 is 5, for 2 is 4, and for 6 is 7 in
nums2
.
- Input:
-
- Input:
nums1 = [9,7,1]
,nums2 = [1,7,9,5,4,3]
- Output:
[-1,9,7]
- Explanation: The next greater number for 9 does not exist, for 7 is 9, and for 1 is 7 in
nums2
.
- Input:
-
- Input:
nums1 = [5,12,3]
,nums2 = [12,3,5,4,10,15]
- Output:
[10,15,5]
- Explanation: The next greater number for 5 is 10, for 12 is 15, and for 3 is 4 in
nums2
.
- Input:
Constraints:
1 <= nums1.length <= nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 10<sup>4</sup>
- All integers in
nums1
andnums2
areunique
. - All the integers of
nums1
also appear innums2
.
Solution
This problem requires us to find the next greater element for each element in nums1
by searching nums2
. The output array contains either the next greater element or -1 if no such element exists.
This problem can be solved using a Monotonic Stack and Hashmap. The Monotonic Stack helps to find the next greater element for each element in nums2
. The Hashmap then maps each element to its next greater element.
Algorithm Walkthrough
- Initialize an empty stack and an empty hashmap.
- Loop through the
nums2
array from left to right. - For each number in
nums2
, while the stack is not empty and the current number is greater than the top element of the stack:- Pop the element from the stack and add an entry to the hashmap with the popped element as the key and the current number as the value.
- Push the current number onto the stack.
- After the loop, any numbers remaining on the stack do not have a next greater element, so for each of these numbers, add an entry to the hashmap with the number as the key and
-1
as the value. - Finally, create an output array by mapping each number in
nums1
to its corresponding value in the hashmap.
Code
Here is the code for this algorithm:
Time and Space Complexity
The time complexity of this algorithm is O(N), where N is the length of nums2
, since each element is pushed and popped from the stack exactly once. The space complexity is O(N) as well, due to the additional space needed for the stack and the hashmap.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible