Watch 10 video solutions for Next Greater Element I, a easy level problem involving Array, Hash Table, Stack. This walkthrough by NeetCode has 117,396 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |