EasyArrayHash TableStackMonotonic Stack

Next Greater Element I

1 approach, code in every language

You are given two arrays, `nums1` and `nums2`, where every element of `nums1` also appears somewhere in `nums2` and all values are distinct. `nums1` is a subset of `nums2`.

For each value `x` taken from `nums1`, locate it inside `nums2` and look at the elements that come after it. The next greater element of `x` is the first value to its right in `nums2` that is strictly larger than `x`. If no such value exists, the answer for that query is `-1`.

Return an array `answer` of the same length as `nums1`, where `answer[i]` is the next greater element for `nums1[i]`.

Example 1

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

Output: [-1,3,-1]

For 4 there is nothing larger to its right, so -1. For 1 the next larger value is 3. For 2 nothing larger follows, so -1.

Example 2

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

Output: [3,-1]

For 2 the next larger value is 3. For 4 there is no larger value to the right, so -1.

Constraints

1 <= nums1.length <= nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 10^4
All integers in nums1 and nums2 are unique.
All integers of nums1 also appear in nums2.

Monotonic Stack + Hash Map

Sweep nums2 once with a decreasing stack, recording the next greater value for every element, then answer each query in O(1).

Loading animation…

Intuition

The heavy work is finding the next greater element for each value in nums2; the nums1 lookups are trivial afterward. Maintain a stack of values that are still waiting for a greater neighbor. As you scan left to right, any time the current value beats the value on top of the stack, the current value is exactly that top's next greater element. Pop every element the current value exceeds and record the mapping. Because each value is pushed and popped at most once, the entire scan is linear. Finally, look up each nums1 value in the map, defaulting to -1.

Algorithm walkthrough

1Create an empty stack and an empty hash map from value to its next greater value.
2Iterate through nums2. For each value cur, while the stack is non-empty and cur is greater than the top, pop the top and record map[top] = cur.
3Push cur onto the stack; it now waits for its own next greater element.
4Any values left on the stack at the end have no greater element to their right, so they simply stay absent from the map.
5Build the result by mapping each element of nums1 through the map, using -1 when the value is missing.

Implementation

class Solution:
    def nextGreaterElement(self, nums1: list[int], nums2: list[int]) -> list[int]:
        next_greater = {}
        stack = []
        for cur in nums2:
            while stack and cur > stack[-1]:
                next_greater[stack.pop()] = cur
            stack.append(cur)
        return [next_greater.get(x, -1) for x in nums1]

Time

O(n + m)

Space

O(n)

n is the length of nums2 and m is the length of nums1. Each nums2 value is pushed and popped once; queries are O(1).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Auction Watchlist Highs is our own problem on the technique behind Next Greater Element I: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free