You get two arrays of distinct integers, nums1 and nums2, where every value of nums1 also appears in nums2. For each x in nums1, find where x sits in nums2 and return the first value to its right in nums2 that is greater than x, or -1 if there is none. Return the answers in the order of nums1.
- 1 <= nums1.length <= nums2.length <= 1000
- 0 <= nums1[i], nums2[i] <= 10^4
- All values are distinct; nums1 is a subset of nums2
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force finds each x in nums2 and scans to its right: O(m * n). Since the values are distinct, the next greater value depends only on the value itself, so we can precompute it for all of nums2. A monotonic stack does that in one pass: while the current value is larger than the stack top, the current value is the top's next greater element. A hash map then answers every query in O(1).
Algorithm
- Create an empty stack and a map
nextfrom value to next greater value. - For each
vinnums2: while the stack top is less thanv, pop it and setnext[top] = v; then pushv. - Values still on the stack have no greater value to the right.
- Build the answer as
next.get(x, -1)for eachxinnums1.
O(m + n)Space: O(n)class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]: nxt = {} # value -> next greater value stack = [] # decreasing values for v in nums2: while stack and stack[-1] < v: nxt[stack.pop()] = v stack.append(v) return [nxt.get(x, -1) for x in nums1]