Leetcode Practice

LC 496. Next Greater Element I

Last updated
Reading time
2 min read

The problem

Solution - O(n∗m)O(n * m) Time

I managed to solve this on my first submission, but my solution wasn't the most optimal. For context, I completed a similar problem beforehand, where I first learned monotonic stacks and the methodology. Wanting to practice similar problems led me to this one.

The idea is to check for increasing values. When found, attempt to update the answer. Because numbers in the second array may not be in the first, the indexOf will return null which prevents setting any unnecessary matches. Also, by initializing the array with -1s, any values that don't have a next greater number are handled from the start.

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  let ans = Array(nums1.length).fill(-1)
  let stack = []
  for (let i = 0; i < nums2.length; i++) {
    while (stack.length && stack[stack.length - 1] < nums2[i]) {
      let val = stack.pop()
      ans[nums1.indexOf(val)] = nums2[i]
    }
    stack.push(nums2[i])
  }

  return ans
}

Optimized Solution - O(n+m)O(n + m) Time

Rather than use .indexOf, this solution stores the first array as a map. The values of the array are used as the keys and the indices are the map's values. Now when setting the answers in the answer array, the index in nums1 can be found instantly.

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  let answer = new Array(nums1.length).fill(-1)
  let stack = []

  // Convert nums1 to a hashmap (O(1) lookup) to avoid using .indexOf (O(n) lookup)
  let hash = {}
  for (let i = 0; i < nums1.length; i++) {
    hash[nums1[i]] = i
  }

  for (let i = 0; i < nums2.length; i++) {
    while (stack.length && stack[stack.length - 1] < nums2[i]) {
      let smallerElement = stack.pop()
      answer[hash[smallerElement]] = nums2[i]
    }
    stack.push(nums2[i])
  }

  return answer
}