Solution: Next Greater Element I

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 in nums2.

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 key-value pair in the hash map with the popped element as the key and the current element of nums2 as the value.

  • This process uses a monotonic stackA monotonic stack maintains elements in either increasing or decreasing order, allowing efficient retrieval of the next greater or smaller elements in a sequence. 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.

  • 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 of nums2 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 $-1$ as their respective values.

• Finally, create an ans array with the same length as nums1 and populate it with the values from the hash map that correspond to the keys in nums1.

• Return the ans array containing the next greater element for each element in nums1.

Let’s look at the following illustration to get a better understanding of the solution: