Next Greater Element I
EasyPrompt
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 <= 10000 <= 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?Approaches
2 approaches with complexity analysis and trade-offs.
This is the most straightforward, brute-force approach. For each element in nums1, we iterate through nums2 to find that element's position. Then, we perform another iteration from that position onwards in nums2 to find the first element that is greater. This involves nested loops, leading to a quadratic time complexity.
Algorithm
- Initialize an integer array
resultof the same size asnums1to store the answers. - Iterate through each element
num1at indexiin thenums1array. - For each
num1, find its index in thenums2array. Let's call thisfoundIndex. - Once
num1is found atfoundIndexinnums2, start another search fromfoundIndex + 1to the end ofnums2. - The first element
nums2[k](wherek > foundIndex) that is greater thannum1is the next greater element. - Store this element in
result[i]and break the inner search. - If the inner search completes without finding any greater element, it means no such element exists. In this case, store
-1inresult[i]. - After iterating through all elements of
nums1, return theresultarray.
Walkthrough
This method directly translates the problem statement into code. For every element in nums1, we find it in nums2 and then scan the rest of nums2 to find the first element that is larger.
- Algorithm:
- Initialize an integer array
resultof the same size asnums1to store the answers. - Iterate through each element
num1at indexiin thenums1array. - For each
num1, find its index in thenums2array. Let's call thisfoundIndex. - Once
num1is found atfoundIndexinnums2, start another search fromfoundIndex + 1to the end ofnums2. - The first element
nums2[k](wherek > foundIndex) that is greater thannum1is the next greater element. - Store this element in
result[i]and break the inner search. - If the inner search completes without finding any greater element, it means no such element exists. In this case, store
-1inresult[i]. - After iterating through all elements of
nums1, return theresultarray.
- Initialize an integer array
class Solution { public int[] nextGreaterElement(int[] nums1, int[] nums2) { int[] result = new int[nums1.length]; for (int i = 0; i < nums1.length; i++) { int currentNum = nums1[i]; int foundIndex = -1; // Find the index of currentNum in nums2 for (int j = 0; j < nums2.length; j++) { if (nums2[j] == currentNum) { foundIndex = j; break; } } // Search for the next greater element from foundIndex + 1 int nextGreater = -1; for (int k = foundIndex + 1; k < nums2.length; k++) { if (nums2[k] > currentNum) { nextGreater = nums2[k]; break; } } result[i] = nextGreater; } return result; }}Complexity
Time
O(m * n), where m is the length of `nums1` and n is the length of `nums2`. For each of the `m` elements in `nums1`, we may have to scan the entire `nums2` array twice in the worst case.
Space
O(m), where m is the length of `nums1`. This space is used for the result array. If the output array is not considered extra space, the complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Requires minimal extra space (only for the output array).
Cons
Highly inefficient for large input arrays, with a quadratic time complexity.
Likely to result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for larger constraints.
Solutions
Solution
class Solution {public int[] nextGreaterElement(int[] nums1, int[] nums2) { Deque<Integer> stk = new ArrayDeque<>(); Map<Integer, Integer> mp = new HashMap<>(); for (int num : nums2) { while (!stk.isEmpty() && stk.peek() < num) { mp.put(stk.pop(), num); } stk.push(num); } int n = nums1.length; int[] ans = new int[n]; for (int i = 0; i < n; ++i) { ans[i] = mp.getOrDefault(nums1[i], -1); } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.