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] <= 104nums1 and nums2 are unique.nums1 also appear in nums2.Follow up: Could you find an
O(nums1.length + nums2.length) solution?This approach involves iterating over each element of nums1 and finding the corresponding element in nums2. Once located, search for the next greater element to its right. This straightforward method checks each pair and ensures correctness but may not be optimal for larger arrays.
This C solution uses nested looping to find the next greater element by directly comparing elements. The outer loop iterates through nums1, and for each element, it finds its position in nums2 using another loop. Then, it looks for the next greater element from that position. Although simple, this solution can be improved in terms of efficiency.
C++
Java
Python
C#
JavaScript
The time complexity of this brute force approach is O(n * m), where n is the number of elements in nums1, and m is the number of elements in nums2. The space complexity is O(1) apart from the output array.
This approach utilizes a stack and a hashmap to efficiently solve the problem. As we traverse nums2, we use the stack to store elements for which the next greater element hasn't been found yet. Whenever a greater element is found, it's recorded in the hashmap against the elements in the stack. This technique is optimal and runs in linear time.
This C solution builds an efficient resolution using a combination of a stack and hashmap. As elements traverse, unmatched elements are pushed onto the stack. When a larger element appears, it is stored in the hashmap mapped to the popped stack elements. This efficient solution runs in O(n) where n is nums2.length.
C++
Java
Python
C#
JavaScript
The time complexity is O(n + m), approaching linear time with respect to input size and space is approximately O(m) for hashmap tracking.
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity of this brute force approach is O(n * m), where n is the number of elements in nums1, and m is the number of elements in nums2. The space complexity is O(1) apart from the output array. |
| Optimized Stack and Hashmap Approach | The time complexity is O(n + m), approaching linear time with respect to input size and space is approximately O(m) for hashmap tracking. |
Next Greater Element | Two Variants | Leetcode • take U forward • 265,567 views views
Watch 9 more video solutions →Practice Next Greater Element I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor