Problem of The Day: Next Greater Element I

Problem Statement

leetcode problem link

Intuition

The problem asks for the next greater element for each number in nums1 based on their positions in nums2. A brute-force approach would involve scanning nums2 for each element in nums1 to find the next greater element, but that would be inefficient. Instead, we can use a monotonic stack to precompute the next greater elements for all items in nums2, which allows us to answer the query for each element in nums1 efficiently.

Approach (Monotonic Decreasing Stack)

We iterate through nums2 from right to left and use a stack to keep track of elements in decreasing order. For each element nums2[i], we remove elements from the stack that are less than or equal to it, since they can’t be the next greater element for any previous numbers. If the stack is not empty after popping, the top element is the next greater element for nums2[i].

We store this mapping in a hash map (hash_map). Initially, we only care about the elements in nums1, but to optimize and allow constant-time lookups, we store results for all elements in nums2.

After building the map, we simply look up the next greater element for each item in nums1 from the hash map.

Complexity

• Time complexity:
  \(O(n + m)\)
  Where (n) is the length of nums2 and (m) is the length of nums1. We process each element in nums2 once using the stack, and then each element in nums1 is processed via hash map lookup.

• Space complexity:
  \(O(n)\)
  We use extra space for the stack and the hash map, both of which can grow up to the size of nums2.

Code

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        stack = []
        hash_map = {i: -1 for i in nums1}
        for i in range(len(nums2) - 1, -1, -1):
            while stack and stack[-1] <= nums2[i]:
                stack.pop()

            hash_map[nums2[i]] = stack[-1] if stack else -1

            stack.append(nums2[i])

        res = []
        for x in nums1:
            res.append(hash_map[x])
        return res

Editorial

Approach 3: Using Stack

class Solution:
    def nextGreaterElement(self, nums1, nums2):
        stack = []
        hashmap = {}

        for num in nums2:
            while stack and num > stack[-1]:
                hashmap[stack.pop()] = num
            stack.append(num)

        return [hashmap.get(i, -1) for i in nums1]