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?Problem Overview: You are given two arrays, nums1 and nums2, where every element of nums1 appears in nums2. For each element in nums1, find the first greater number to its right in nums2. If no greater value exists, return -1. The challenge is efficiently locating the next greater element without repeatedly scanning the entire array.
Approach 1: Brute Force Scan (Time: O(n*m), Space: O(1))
Start by locating each element of nums1 inside nums2. Once found, iterate to the right of that position until you encounter a larger value. If a larger value appears, record it as the answer; otherwise return -1. This approach uses simple iteration over the array but repeatedly scans portions of nums2, which leads to quadratic behavior in the worst case. It works for small inputs and is useful for understanding the core requirement: scanning to the right for a larger element.
Approach 2: Monotonic Stack + Hash Map (Time: O(n + m), Space: O(n))
The optimized solution preprocesses nums2 using a monotonic stack. Traverse nums2 from left to right while maintaining a decreasing stack. When the current number is greater than the stack’s top element, pop elements from the stack and record their next greater value in a hash table. This means you discovered the first larger number to their right. Push the current element onto the stack and continue scanning.
After processing the entire array, the hash map stores the next greater value for every relevant number in nums2. Elements left in the stack have no greater element, so their result remains -1. Finally, iterate through nums1 and perform constant-time hash lookups to retrieve the precomputed answers. Each element is pushed and popped at most once from the stack, giving linear complexity.
The key insight is preprocessing the larger array so queries become constant-time lookups. Instead of repeatedly searching to the right, the stack identifies next-greater relationships in a single pass.
Recommended for interviews: Interviewers expect the monotonic stack solution. The brute force method demonstrates you understand the problem but does not scale well. Recognizing that this is a classic “next greater element” pattern and solving it with a decreasing stack shows strong pattern recognition and familiarity with stack-based array processing.
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.
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.
The time complexity is O(n + m), approaching linear time with respect to input size and space is approximately O(m) for hashmap tracking.
We can traverse the array nums2 from right to left, maintaining a stack stk that is monotonically increasing from top to bottom. We use a hash table d to record the next greater element for each element.
When we encounter an element x, if the stack is not empty and the top element of the stack is less than x, we keep popping the top elements until the stack is empty or the top element is greater than or equal to x. At this point, if the stack is not empty, the top element of the stack is the next greater element for x. Otherwise, x has no next greater element.
Finally, we traverse the array nums1 and use the hash table d to get the answer.
The time complexity is O(m + n), and the space complexity is O(n). Here, m and n are the lengths of the arrays nums1 and nums2, respectively.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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. |
| Monotonic Stack | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n * m) | O(1) | Simple baseline solution or when input sizes are very small |
| Monotonic Stack + Hash Map | O(n + m) | O(n) | General case and interview-preferred approach for next greater element problems |
Next Greater Element I - Leetcode 496 - Python • NeetCode • 117,396 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