EasyArrayHash TableStackMonotonic StackUpdated Sep 2026

496. Next Greater Element I

Asked at Flipkart

Difficulty

Easy

Time

O(m + n)

Space

O(n)

Pattern

Array

Companies

1

Problem

You get two integer arrays, nums1 and nums2. Every value in nums1 also appears in nums2, and all values in both arrays are distinct (no repeats).

For each value v in nums1, look at where v sits inside nums2. Then walk to the right from that position and find the first value that is strictly bigger than v. That value is the answer for v. If nothing to the right is bigger, the answer is -1.

Return an array ans of the same length as nums1, where ans[i] is the answer for nums1[i], in the same order as nums1. The order of nums1 matters — do not sort it.

Find the first bigger value to the right

nums213420123The value 4 sits at index 2; only 2 is to its right,and 2 < 4, so the answer is -1.nums213420123The value 1 sits at index 0; the first bigger value toits right is 3, so the answer is 3.answer-13-1012Answers follow the order of nums1 = [4, 1, 2], so weget [-1, 3, -1].
For each value of nums1, look at its position in nums2 and take the first larger value on the right, or -1 if there is none.

Constraints

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

Examples

Example 1
Inputnums1 = [4,1,2], nums2 = [1,3,4,2]
Output[-1,3,-1]
WhyIn nums2, 4 is at index 2 and only 2 is to its right, which is smaller, so 4 gets -1. The 1 at index 0 has 3 right next to it, and 3 > 1, so 1 gets 3. The 2 at index 3 is the last element, so nothing is to its right and it gets -1.
Example 2
Inputnums1 = [2,4], nums2 = [1,2,3,4]
Output[3,-1]
WhyThe 2 sits at index 1 of nums2, and the first bigger value to its right is 3. The 4 is the last element of nums2, so no bigger value exists to its right and it gets -1.

Asked At

1 companies
CompanyDifficulty
FlipkartEasyView all Flipkart questions →

How to Think About It

1

Brute force: for each value in nums1, find it in nums2 and scan right for a larger number. That is O(m * n).

2

Key insight: compute the next greater element for every value of nums2 once, store it in a hash map, then answer nums1 with lookups.

3

Use a monotonic decreasing stack while scanning nums2. When the current number is larger than the top of the stack, it is the next greater element for that top — pop and record. Then push the current number.

4

Walkthrough on nums2 = [1,3,4,2]: push 1; 3 > 1 -> next[1] = 3, push 3; 4 > 3 -> next[3] = 4, push 4; 2 < 4, push 2. Leftovers 4 and 2 get -1.

5

All values are distinct, so a value-keyed map is safe.

Optimal Approach

Step 1: nxt = {}, stack = [].
Step 2: For each x in nums2:
While stack and stack[-1] < x: nxt[stack.pop()] = x.
Push x.
Step 3: Return [nxt.get(v, -1) for v in nums1].

Each element of nums2 is pushed and popped at most once.

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

Monotonic stack over nums2

stack1← topRead 1 from nums2: the stack is empty, so just push 1.stack3← topRead 3: 3 > 1, so pop 1 and record next[1] = 3, thenpush 3.stack42← topRead 4: pop 3 and record next[3] = 4, push 4. Read 2:2 < 4, so push 2.while stack and stack[-1] < x: nxt[stack.pop()] = xstack.append(x)leftovers get -1
Keep a decreasing stack. When a new value is bigger than the top, it is the next greater element for that top.
ComplexityTime O(m + n)Space O(n)We scan nums2 once and each value is pushed and popped from the stack at most once; the map and stack both hold up to n entries.

What Trips People Up in Real Interviews

1

Searching nums2 for each nums1 value. It works but is quadratic; precompute with the stack instead.

2

Using an increasing stack. You need a decreasing stack so that a larger value can resolve every smaller value waiting on it.

3

Forgetting that unresolved values get -1.

4

Confusing "next greater" (first larger to the right) with "maximum to the right".

Solution Code

O(m + n) time
def nextGreaterElement(nums1, nums2):
    nxt = {}
    stack = []
    for x in nums2:
        while stack and stack[-1] < x:
            nxt[stack.pop()] = x
        stack.append(x)
    return [nxt.get(v, -1) for v in nums1]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Next Greater Element I problem?

Next Greater Element I gives you `nums1`, a subset of `nums2`, and asks, for each value in `nums1`, for the first larger value to its right in `nums2` (or `-1`). It is the gateway problem for the monotonic stack pattern.

How do you solve Next Greater Element I?

The optimal approach runs in O(m + n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Next Greater Element I?

Next Greater Element I is asked at Flipkart. It is a easy difficulty problem.

What are common mistakes on Next Greater Element I?
  • Searching `nums2` for each `nums1` value. It works but is quadratic; precompute with the stack instead.
  • Using an increasing stack. You need a decreasing stack so that a larger value can resolve every smaller value waiting on it.
  • Forgetting that unresolved values get `-1`.
  • Confusing "next greater" (first larger to the right) with "maximum to the right".