Next Greater Element I

EasystackMonotonic stackstackmonotonic-stackhash-map

Maintained by Vikas Dulgunde, 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

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]

Output: [-1,3,-1]

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.

Input: nums1 = [2,4], nums2 = [1,2,3,4]

Output: [3,-1]

The first value larger than 2 to its right is 3. Nothing follows 4, so its answer is -1.

Input: nums1 = [1,3], nums2 = [3,1,2]

Output: [2,-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.

Loading the editor...

Approaches

Brute force

Time O(m * n) where m is nums1 length and n is nums2 length · Space O(1) beyond the output

For 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 map

Precompute 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.

Build the rest of your prep

All coding problems

Practice problems by company

The NeetCode 150 roadmap

Guide: coding interview patterns

Examples

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]

Output: [-1,3,-1]

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.

Input: nums1 = [2,4], nums2 = [1,2,3,4]

Output: [3,-1]

The first value larger than 2 to its right is 3. Nothing follows 4, so its answer is -1.

Input: nums1 = [1,3], nums2 = [3,1,2]

Output: [2,-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.

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 output

For 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 map

Precompute 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.

Next Greater Element I

Examples

Constraints

Hints

Approaches

Brute force

Monotonic stack with hash map

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep

Next Greater Element I

Examples

Constraints

Hints

Approaches

Brute force

Monotonic stack with hash map

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep