Solution: Next Greater Element I
Let's solve the Next Greater Element I problem using the Hash Map pattern.
Statement
Given the two distinct integer arrays, nums1
and nums2
, where nums1
is a subset of nums2
, find all the next greater elements for nums1
values in the corresponding places of nums2
.
In general, the next greater element of an element, $x$, in an array is the first greater element present on the right side of $x$ in the same array. However, in the context of this problem, for each element $x$ in nums1
, find the next greater element present on the right side of $x$ in nums2
and store it in the ans
array. If there is no such element, store $1$ for this number. The ans
array should be of the same length as nums1
, and the order of the elements in the ans
array should correspond to the order of the elements in nums1
.
Return the ans
array after finding the next greater elements.
Note: The input data may or may not be sorted.
Constraints:
 $1 \leq$
nums1.length
$\leq$nums2.length
$\leq 10^3$  $0 \leq$
nums1[i]
,nums2[i]
$\leq 10^4$ nums1
have distinct integers.nums2
have distinct integers. All integers in
nums1
also appear innums2
.
Solution
Youâ€™ve probably brainstormed some approaches and have an idea of how to solve this problem. Letâ€™s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and implementation constraints.
Naive approach
The naive approach is to select each element of nums1
and search for its occurrence in nums2
. If the element is found, we look for the occurrence of its next greater element in nums2
linearly. If the next greater element is obtained, we store it in the ans
array in the corresponding place to the element in nums1
. Otherwise, we store $1$ in the ans
array for that element.
The overall time complexity of the algorithm becomes $O(n_1 \times n_2)$, because weâ€™re searching for each element of the nums1
array in the nums2
array. The space complexity of this algorithm is $O(1)$.
Optimized solution using hash map
An optimized approach to solve this problem is using a hash map and a stack. A hash map is used to store the elements in nums2
as keys and their next greater elements as the respective values.
The algorithm proceeds through the following steps after creating an empty stack and a hash map:

Iterate over each element of
nums2
, and if the stack is not empty, compare it with the top element of the stack.
If the current element of
nums2
is greater than the top element of the stack, pop the top element from the stack and put a keyvalue pair in the hash map with the popped element as the key and the current element ofnums2
as the value. 
This process uses a
that maintains elements in decreasing order, ensuring that the top of the stack always has the smallest element yet to find its next greater element. This allows efficient resolution of next greater elements.monotonic stack A monotonic stack maintains elements in either increasing or decreasing order, allowing efficient retrieval of the next greater or smaller elements in a sequence. 
Repeat the step above until either the stack becomes empty or the current element of
nums2
is not greater than the top element of the stack.


After each iteration over
nums2
, push the current element ofnums2
onto the stack. 
After processing all the elements of
nums2
, check if any elements are still remaining in the stack. If they are, pop them and put keyvalue pairs in the hash map with the remaining elements as the keys and $1$ as their respective values. 
Finally, create an
ans
array with the same length asnums1
and populate it with the values from the hash map that correspond to the keys innums1
. 
Return the
ans
array containing the next greater element for each element innums1
.
Letâ€™s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ handson prep courses.