Next Greater Element

Difficulty: Easy

Problem

You get two distinct 0-indexed integer arrays, nums1 and nums2, where every value of nums1 also appears in nums2, and all the numbers within an array are different (so a number names exactly one place). Each number x of nums1 is a question about its place in nums2: look at its position in nums2 and move rightwards to find the first value strictly larger than x; that is its next greater element. If nothing larger lies to the right, the answer for x is -1. Return the answers in the order of nums1.

Example

Input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]
Explanation: For 4 in nums2 = [1, 3, 4, 2]: only 2 lies to its right and 2 < 4, so the answer is -1. For 1: the value right after it is 3 > 1, so the answer is 3. For 2: it is the last element, so nothing is to its right and the answer is -1. (All numbers within each array are different, so each number names exactly one place in nums2.)

Brute-force approach

For each element in nums1, find it in nums2, then scan rightward in nums2 for the first greater element.

Steps

  1. For each element x in nums1:
  2. Find x's index in nums2
  3. Scan from that index to the right for first element > x
  4. If found, record it; otherwise record -1

Time complexity: O(m × n) · Space complexity: O(1)

Trade-offs

  • For each of m elements in nums1, we may scan up to n elements in nums2
  • Redundant: we may re-scan the same portion of nums2 for different queries
  • O(m × n) is too slow for large inputs

Optimal approach

Key insight: As we traverse nums2, elements waiting for their 'next greater' sit in a decreasing stack. A new larger element resolves all of them at once.

Process nums2 with a monotonic decreasing stack. For each element, pop all smaller stack elements (they found their next greater). Store results in a hash map for O(1) lookup.

Steps

  1. Initialize an empty stack and a hash map
  2. For each num in nums2:
  3. While stack is not empty and stack.top < num: pop and record answer[popped] = num
  4. Push num onto the stack
  5. For each num in nums1: result = answer.get(num, -1)

Time complexity: O(n + m) · Space complexity: O(n)

Pseudocode

function nextGreaterElement(nums1, nums2):
    answer = {}
    stack = []
    
    for num in nums2:
        while stack not empty and stack.top < num:
            answer[stack.pop()] = num
        stack.push(num)
    
    result = []
    for num in nums1:
        result.push(answer.get(num, -1))
    return result

Hints

  • Use a monotonic decreasing stack to find next greater elements efficiently
  • When a larger element appears, it is the 'next greater' for all smaller elements currently on the stack
  • Use a hash map to store each element's next greater element for O(1) lookup, and read it back with answer.get(num, -1) so a missing number gives -1
  • One arrival can answer several waiting numbers at once: on nums2 = [6, 4, 2, 9, 5] the 9 pops 2, 4 and 6 in a row

Complexity questions

What is the time complexity of the brute force approach?

O(m × n). For each of m elements in nums1, we may scan up to n elements in nums2 → O(m × n).

What is the time complexity of the monotonic stack approach?

O(m + n). We process nums2 once with the stack in O(n). Each element is pushed/popped at most once. Then we look up m elements in O(m). Total: O(n + m).

What is the space complexity of the monotonic stack approach?

O(n). The hash map and stack can each hold up to n elements from nums2 → O(n) space.

The stack code has a while loop inside a for loop. Why is the stack approach still O(n) over nums2 and not O(n²)?

Each number is pushed once and popped at most once, so all the while loops together do at most n pops. A single arrival can pop many numbers, but a popped number is gone for good. Over the whole scan every number is pushed once and popped at most once, so the pops add up to at most n → O(n) in total.

Check your understanding of Next Greater Element

What does 'next greater element' mean for a number in nums2?

The first element to the right that is greater than it. The next greater element is the first element scanning rightward from the number's position that has a larger value.

For nums2 = [1, 3, 4, 2], what is the next greater element for 4?

-1 (no greater element to its right). Looking right from 4 in [1, 3, 4, 2]: only 2 remains, and 2 < 4. There is no element greater than 4 to its right, so the answer is -1.

For nums2 = [1, 3, 4, 2], what is the next greater element for 3?

4. Looking right from 3 in [1, 3, 4, 2]: the first element greater than 3 is 4.

Related problems

Keep practising