Pattern this teaches:Monotonic Stack
Next Greater Element I
An easy Stack interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Stack
- Sheets
- 2
- Core for
- 9 roles
The problem
Every value of nums1 also appears somewhere in nums2. For each value in nums1, find where it sits in nums2 and look to its right for the first larger number; record that number, or -1 when nothing to the right is larger.
Example 1
- Input
- nums1 = [6,2,5], nums2 = [2,6,3,5]
- Output
- [-1,6,-1]
- Why
- After 6 in nums2 nothing is larger; after 2 the next greater is 6; after 5 nothing follows.
Example 2
- Input
- nums1 = [3,7], nums2 = [9,3,5,7]
- Output
- [5,-1]
- Why
- After 3 the next greater is 5; 7 is last with nothing greater after it.
Constraints
- 1 <= nums1.length <= nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 10^4
- All integers in nums1 and nums2 are unique
- Each element of nums1 also appears in nums2
How to think about it
Updated 2026-09-29The subset condition is a decoy: nums1 only specifies which questions to answer, while all structural information lives in nums2. If you solve next greater element for every item in nums2 all at once and cache the results in a hash map, answering queries for nums1 becomes a sequence of instant hash table lookups.
Approaches, worst first
Brute force search per query
time O(nums1.length * nums2.length) · space O(1)
For each element in nums1, locate its position in nums2 with a linear scan, then continue scanning right until finding a strictly larger value. Loses because repeated scans over nums2 re-evaluate the same rightward sequences for each query.
Monotonic stack with hash map cacheWrite this one
time O(nums1.length + nums2.length) · space O(nums2.length)
Traverse nums2 while maintaining a monotonic decreasing stack of values. When the current value exceeds the top of the stack, pop each smaller value and record `map[popped] = current`. After nums2 is processed, any value remaining on the stack maps to -1. Map nums1 via the table.
Where people lose marks · 2
- Looking for the next greater element in nums1 itself instead of nums2: the search array is nums2, while nums1 merely dictates output ordering.
- Assuming nums2 elements left on the stack at the end have a greater element: unpopped keys must resolve to -1.
The theory behind it
Stack — the ground this problem stands on. All Stack problems
What Stack is
A stack is a vertical pile of cafeteria trays where items enter and depart from one single opening at the top. The most recent item set down is the first one retrieved, while items deposited earlier remain buried underneath until newer arrivals are lifted away. This strict last-in, first-out sequence guarantees that older context stays preserved until all newer nested actions run to completion.
When to reach for it
Reach for a stack whenever an algorithm encounters nested structures like matched brackets, tags, or algebraic formulas. Problems demanding undo operations, function execution histories, or evaluating postfix arithmetic require this discipline. It is also the primary structure for monotonic queries where a task asks for the nearest greater or smaller value adjacent to each position in a series.
How the pattern works
Picture peeling layers back in exact reverse order of their arrival. Push items as pending jobs or unclosed delimiters encounter the scan. When closing boundaries appear, pop the topmost entry and check for compatibility. For monotonic patterns, maintain an invariant where elements on the stack remain strictly increasing or decreasing; pop any items that violate this rule before recording candidate answers and pushing the current item.
More Stack problems
Target Roles
Core requirement for 9 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .