Next Greater Element I
Problem Description
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 <= 1000
- 0 <= nums1[i], nums2[i] <= 104
- All integers in
nums1andnums2are unique. - All the integers of
nums1also appear innums2.
Follow up: Could you find an O(nums1.length + nums2.length) solution?
Solve it on LeetCode
Approaches
1. Brute Force
The brute force approach is straightforward: For each element in nums1, search for its next greater element in nums2.
Intuition:
- For each element in
nums1, iterate overnums2to find the index of that element. - From that index, search for the first element greater than the current element.
- If a greater element is found, add it to the result, otherwise, append -1 (indicating no greater element found).
Code:
- Time Complexity: O(n * m), where n is the length of
nums1and m is the length ofnums2. For each element innums1, we do a potentially full scan ofnums2. - Space Complexity: O(1), apart from the space used to store the result.
2. Using a Stack and HashMap
This approach leverages a stack and hashmap to efficiently find the next greater element for all elements in nums2 in a single pass.
Intuition:
- Use a stack to track elements for which we are finding the next greater element.
- As we iterate
nums2, for each element, pop elements from the stack if the current element is greater because the current element is the "next greater" for those popped elements. - Map each popped element to the current element in a hashmap.
- After processing, for each element in
nums1, retrieve the next greater element directly from the hashmap.
Code:
- Time Complexity: O(n + m), iterating nums2 once O(m), and checking each nums1 element in O(1) using the hashmap.
- Space Complexity: O(m), for storing the hashmap and the stack.