DSA AnimatorDSA animations
Next Greater Element I LC #496 Easy Monotonic Stack · HashMap
Problem

The next greater element of some element x in array nums2 is the first element to the right of x in nums2 that is strictly greater. Given nums1 (a subset of nums2), for each element in nums1, find its next greater element in nums2. Return -1 if it does not exist.

Example 1
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: 4 has no greater→-1; 1→next greater is 3; 2→no greater→-1.
Example 2
Input: nums1 = [2,4], nums2 = [1,2,3,4]
Output: [3,-1]
Explanation: 2→next greater is 3; 4→no greater→-1.
Constraints: 1 ≤ nums1.length ≤ nums2.length ≤ 1000  |  All integers in nums1 and nums2 are unique.
Try Examples
Custom:
nums2 — Source Array
Monotonic Stack (decreasing, bottom→top)
stack (top↑)
Next-Greater Map element → nextGreater
{ }
nums1 — Query Results
Variables
i (nums2)
—
nums2[i]
—
stack top
—
map size
0
Step Logic
Select an example above and press Play.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Init empty map and stack
2
For each n in nums2: while stack top < n, pop and record map[top] = n
3
Push n onto the stack (stack stays decreasing)
4
Remaining stack elements have no next greater → implicitly -1
5
For each element in nums1: look up in map, default -1
Time
O(n+m)
Space
O(n)
Why Monotonic Stack Works

We keep the stack in decreasing order. When a new element n is encountered and it is larger than the top, that top element has finally found its next greater element. We pop and record it. Elements that never get popped have no next greater element (they remain -1). The HashMap then gives O(1) lookup for any query in nums1.

How to solve Next Greater Element I

LeetCode 496 · Easy · Stack · Pattern: Monotonic Stack

Why the obvious approach is slow

Searching nums 2 for each number and scanning right is O(n·m). Instead, compute the next greater element for all of nums 2 once.

The key idea

Walk through nums 2 with a decreasing stack. When a bigger number arrives, it is the next greater element for everything smaller on the stack. Store those answers in a hash map, then look up each number of nums 1.

Remember

One monotonic stack pass finds the next greater element for everything. A hash map answers the queries afterwards.

Run the animation above on your own input, or watch the 1:23 video explanation of Next Greater Element I with a dry run and Java code.

More Stack problems