Next Greater Element I

Tips

Problem Type: Monotonic Stack

Problem

You are given two arrays nums1 and nums2 with no duplicate elements, where nums1 is a subset of nums2.

Find all the next greater numbers for nums1's elements in the corresponding places of nums2.

The next greater element of an element x in nums1 is the first greater element to the right of x in nums2. If it does not exist, return -1 for this element.

Example

Input: nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]

Output: [-1, 3, -1]

Explanation:

For number 4 in nums1, you cannot find the next greater number for it in the second array (there is only 2 to the right of 4 in nums2), so the output is -1.

For number 1 in nums1, the next greater number for it in the second array is 3.

For number 2 in nums1, there is no next greater number for it in the second array, so the output is -1.

Solution

Tips

A monotonic stack is essentially a stack where elements maintain a specific order (monotonically increasing or decreasing) after each new element is pushed.

The diagram below provides great insight: imagine array elements as people standing side by side, with element values representing their heights. Take the first element 2 as an example - looking to the right, the subsequent 1 and 2 are blocked from view, and you can only see 4. Therefore, the next greater element for 2 is 4. Similarly, when the second element 1 looks to the right, the first visible element is 2, so the next greater element for 1 is 2.

496-next-greater-element

Brute Force
Monotonic Stack - JavaScript
Monotonic Stack - Rust

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function (nums1, nums2) {
  const result = new Array(nums1.length).fill(-1)

  for (let i = 0; i < nums1.length; i++) {
    for (let j = 0; j < nums2.length; j++) {
      if (nums2[j] === nums1[i]) {
        for (k = j + 1; k < nums2.length; k++) {
          if (nums2[k] > nums1[i]) {
            result[i] = nums2[k]
            break
          }
        }
      }
    }
  }

  return result
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function (nums1, nums2) {
  const map = new Map()
  const stack = []

  for (const num of nums2) {
    while (stack.length > 0 && stack[stack.length - 1] < num) {
      map.set(stack.pop(), num)
    }

    stack.push(num)
  }

  const n = nums1.length
  const res = new Array(n).fill(-1)

  for (let i = 0; i < n; i++) {
    if (map.has(nums1[i])) {
      res[i] = map.get(nums1[i])
    }
  }

  return res
}

use std::collections::HashMap;

    pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let mut map = HashMap::new();
        let mut stack = vec![];

        for num in nums2 {
            while !stack.is_empty() && stack[stack.len() - 1] < num {
                map.entry(stack[stack.len() - 1])
                    .and_modify(|e| *e = num)
                    .or_insert(num);
                stack.pop();
            }

            stack.push(num);
        }

        let mut res = vec![-1; nums1.len()];
        for (i, num) in nums1.iter().enumerate() {
            if let Some(x) = map.get(&num) {
                res[i] = *x;
            }
        }

        res
    }

Problem​

Solution​

Problem

Solution