Next Greater Element I
Maintained by Vikas D, software engineer
You receive two arrays of distinct integers, nums1 and nums2. Every value in nums1 also occurs somewhere in nums2, so nums1 acts as a list of lookups into nums2.
For a value x, its next greater element is found by walking rightward from x inside nums2 and taking the first value you meet that exceeds x. The scan happens only in nums2, never in nums1, and it stops at the first larger value.
Build a result array the same length as nums1. The entry at position i is the next greater element for nums1[i], or -1 when no value to the right of x in nums2 is larger.
Because all values are distinct, each query has exactly one position in nums2, which keeps the lookup unambiguous.
Examples
4 sits at the end-region with only 2 after it, so -1. After 1 comes 3, which is larger, so 3. After 2 there is nothing, so -1.
The first value larger than 2 to its right is 3. Nothing follows 4, so its answer is -1.
nums1 order does not have to match nums2. After 1 in nums2 comes 2, which is larger, giving 2. Nothing to the right of 3 is larger, giving -1.
Constraints
- 1 <= nums1.length <= nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 10^4
- All integers across both arrays are unique
- Every value in nums1 also appears in nums2
Visible test cases
- nextGreaterElement([4,1,2], [1,3,4,2]) == [-1,3,-1]
- nextGreaterElement([2,4], [1,2,3,4]) == [3,-1]
- nextGreaterElement([1], [1]) == [-1]
- nextGreaterElement([3], [1,2,3,4,5]) == [4]
- nextGreaterElement([5,3,1], [5,4,3,2,1]) == [-1,-1,-1]
- nextGreaterElement([1,3], [3,1,2]) == [2,-1]
Hints
Hint 1
The answer for each query depends only on what happens to the right of its value inside nums2, so the lookup positions in nums1 are independent of one another.
Hint 2
If you precompute the next greater element for every value in nums2 once, answering each nums1 query becomes a single map read.
Hint 3
Scan nums2 and keep a stack of values still waiting for a larger value. When the current value beats the values on top of the stack, you have just found their next greater element.
Approaches
Brute force
Time O(m * n) where m is nums1 length and n is nums2 length · Space O(1) beyond the outputFor each query value, locate it in nums2 and scan forward until a larger value appears.
- For each value in nums1, find its index in nums2.
- Walk from that index toward the end of nums2.
- Return the first value greater than the query, or -1 if the walk ends with no larger value.
- Collect the answers in order to form the result.
Monotonic stack with hash map
Time O(m + n) · Space O(n) for the stack and mapPrecompute the next greater element for every value in nums2 in one pass using a decreasing stack, then answer each query in constant time.
- Create an empty map and an empty stack.
- Iterate over nums2. While the stack is non-empty and the current value exceeds the stack top, pop that top and record current as its next greater element in the map.
- Push the current value onto the stack.
- Any values left on the stack at the end have no greater element to their right, so they default to -1.
- Map each value in nums1 through the map, falling back to -1 when the value is absent.
Common mistakes
- Searching for the next greater element inside nums1 instead of nums2. The scan must always happen in the reference array.
- Returning a larger value found anywhere to the right rather than the FIRST larger value, which changes the answer.
- Forgetting that values left on the stack after the scan have no next greater element and must resolve to -1.
- Assuming nums1 follows the same order as nums2; the queries can appear in any order.
Follow-up variations
- Next Greater Element II, where nums2 is circular so the search wraps around past the end.
- Allow duplicate values, which breaks the one-position-per-value assumption and forces you to track indices rather than values.
- Answer the queries as an online stream where nums1 values arrive one at a time after nums2 is fixed.