Next Greater Element

Difficulty: Easy

Problem

You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2. For each element in nums1, find the next greater element of that number in nums2. The next greater element of a number x in nums2 is the first number to the right of x in nums2 that is greater than x. If no such number exists, return -1 for that element.

Example

Input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]
Output: [-1, 3, -1]
Explanation: For 4 in nums2 = [1, 3, 4, 2]: scan right from 4 → only 2 remains, 2 < 4 → no greater element → -1. For 1: scan right from 1 → 3 > 1 → next greater is 3. For 2: last element, nothing to the right → -1.

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 map[popped] = num
  4. Push num onto the stack
  5. For each num in nums1: result = map[num] or -1

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