Solution: Next Greater Element
Let's solve the Next Greater Element 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, , in an array is the first greater element present on the right side of in the same array. However, in the context of this problem, for each element in nums1
, find the next greater element present on the right side of in nums2
and store it in the ans
array. If there is no such element, store 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:
-
nums1.length
nums2.length
-
nums1[i]
,nums2[i]
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 in the ans
array for that element.
The overall time complexity of the algorithm becomes , because we’re searching for each element of the nums1
array in the nums2
array. The space complexity of this algorithm is .
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 key-value 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 key-value pairs in the hash map with the remaining elements as the keys and 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+ hands-on prep courses.