496. Next Greater Element I

496

EasyMonotonic Stack and Monotonic QueueMonotonic decreasing stack plus hash mapNext greater element with lookup indirection

Next Greater Element I

Given two distinct-valued arrays nums1 and nums2 where nums1 is a subset of nums2, for each element of nums1 find the next greater element to its right within nums2. Return an array where each position holds that next greater value, or -1 if none exists.

Open official problem prompt ↗

In plain English

For each queried value, report the first strictly larger number appearing to its right in the reference array, or -1.

Picture it like this

People of different heights walk past a doorway. Each shorter person waits to note the first taller person who follows them; you jot each match in a notebook, then answer any 'who was next taller than X' question instantly.

Example

Input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]
Why: In nums2, 4 has nothing greater to its right (-1), 1's next greater is 3, and 2 has nothing greater to its right (-1).

Constraints

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

Pattern lesson

See the pattern, then code

Next greater element with lookup indirection

↗

Monotonic Stack and Monotonic Queue

Next greater or smaller value, nearest boundary, histogram, or window extremum.. Precompute the next greater element for every value in nums2 in one pass with a decreasing stack: when a larger number arrives it is the next greater element for all smaller values still on the stack. Then answer each nums1 query with an O(1) hash-map lookup.

New words, made simpleKnow these before the algorithm

Next greater element: The first value to the right that is strictly larger than the current one.
Lookup indirection: Solving the general problem once over nums2 and answering nums1 queries via a hash map instead of re-scanning.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Nested search

Works within the small constraints but wastes the structure; slower than needed.

For each nums1 value find it in nums2, then scan right for a larger value.

Time O(n * m)Space O(1)

Best choiceMonotonic stack + map

Linear and cleanly separates precomputation from queries.

Precompute all next-greater answers for nums2 in one pass, then O(1) lookups.

Time O(n + m)Space O(n)

The rule we keep true

Invariant

The stack holds values from nums2 in strictly decreasing order that are still awaiting a greater element to their right.

Why this is correct

Reasoning

When value x is processed, every stacked value smaller than x has just met its first larger right-neighbor (x itself), because they were pushed earlier and nothing larger appeared until now. Recording that mapping and popping them keeps the stack decreasing; any value never popped truly has no greater element and defaults to -1.

The algorithm in three movesSay these aloud before coding

1Iterate nums2 with a decreasing monotonic stack of values

x=3 pops 1 -> ng[1]=3, stack=[3]

2While the current value exceeds the stack top, pop it and map top -> current value

x=4 pops 3 -> ng[3]=4, stack=[4]

3Push the current value; values left on the stack have no greater element

x=2: stack=[4,2]; ng={1:3, 3:4}

4Build the result by looking up each nums1 value, defaulting to -1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readx = 3

2 · AskDoes 3 resolve the top?

3 · Update statestack = [1]

4 · Result1 < 3 so ng[1] = 3; push 3, stack = [3].

Key takeaway

Scanning nums2, each larger value resolves the smaller values waiting on the stack (1 -> 3, 3 -> 4).

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Prepare map and stack
The map will hold value -> next greater; the stack tracks unresolved decreasing values.
2
Lines 5-8Resolve on a bigger value
Each smaller stacked value gets x as its next greater, then x is pushed as the newest unresolved value.
3
Lines 9Answer queries
Every nums1 value is looked up in O(1); missing keys default to -1 since they had no greater element.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

The maximum value of nums2 always maps to -1
A nums1 value at the far right of nums2 yields -1
nums1 equal to nums2 returns the full next-greater array

Common beginner mistakes

Using <= instead of < when popping, which is wrong for a strictly-greater requirement (though values are unique here)
Scanning nums1 directly instead of precomputing over nums2, losing the linear-time benefit
Forgetting the -1 default for values still on the stack at the end

Check your understanding

Why can we precompute answers for all of nums2 even though we only need nums1's values?

Next Greater Element I

Next Greater Element I

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Monotonic Stack and Monotonic Queue