Leetcode: 496. Next Greater Element I

Problem Statement: Given two arrays \(q\) (queries) and \(v\) (values) with unique integers, return for each query \(i\) the next greater integer of \(b[j]\) where \(b[j]=q[i]\) or -1 if it doesn't exist.

As the problem asks for a solution \(O(|q|+|v|)\), we must compute all next greater elements of \(v\) in \(O(|v|)\) and use them to answer to each query. From the definition of the problem, if \(|q|=1\) then the return value should be \([-1]\) since there is no next greater element. The same is true for any last integer on \(v\). Suppose that we are processing \(v[0]\) and \(v[0]>v[1]\). At this point, we don't know the answer. Be \(i\) the first index where \(v[i]>v[0]\) and \(j\) the first index where \(v[j]>v[1]\). If \(i=j\), we know that \(i\) is the answer not only for \(v[0]\) and \(v[1]\) but for all indexes from 0 to \(i-1\), since \(v[0]>v[1]>...>v[i-1]\). Otherwise, \(i\) must be greater than \(j\), so only some of the integer in \(v[1..(j-1)]\) found their next greater integer. We can keep the unanswered integers in a stack (Monotonic Stack), and pop all of then that are lesser than the number being processed; on the end, we can add the current number to the stack and continue to process the next one. To answer the queries efficiently, we can use a dictionary from integers in \(b\) to next greater integer.

• Time complexity: \(O(|q| + |v|)\)
• Space complexity: \(O(|v|)\)

from collections import deque


def solve(nums1, nums2):
    greaters = {}
    stack = deque(maxlen=len(nums2))
    for num in nums2:
        while len(stack) and stack[-1] < num:
            greaters[stack.pop()] = num
        stack.append(num)

    return [greaters.get(num, -1) for num in nums1]


assert solve([4,1,2], [1,3,4,2]) == [-1,3,-1]
assert solve([2,4], [1,2,3,4]) == [3,-1]


class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return solve(nums1, nums2)