Sweaty Imposter

Next Greater Element I

EasyMonotonic Stack/QueueJuniorOpen on LeetCodeUpdated

You're given two arrays of distinct integers, nums1 and nums2, where every value in nums1 also appears in nums2. For each value x in nums1, find x in nums2 and look to its right for the first value larger than x. Return an array holding that value for each element of nums1, in nums1's order, using -1 when nothing larger comes after x in nums2.

Examples

nums1 = [4,1,2], nums2 = [1,3,4,2] returns [-1,3,-1]

In nums2, 4 is followed only by 2, which is smaller, so its answer is -1. 1 is followed immediately by 3. 2 is the last element of nums2, so nothing follows it and its answer is -1.

nums1 = [2,4], nums2 = [1,2,3,4] returns [3,-1]

Right after 2 in nums2 comes 3, the first larger value. 4 is the last element of nums2, so its answer is -1.

Constraints

  • 1 <= nums1.length <= nums2.length <= 1000
  • All values unique.

Hints

Hint 1

If you scanned nums2 once, which earlier values would be 'waiting' for a bigger number to show up?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Work out the answer once for every value in nums2, then look up the elements of nums1. Scan nums2 left to right with a stack of values still waiting for something larger, which stays decreasing. When num arrives, pop every smaller value and record num as its next greater element in a map, then push num. Values never popped have none, so lookups default to -1. Each value is pushed and popped once (n = len(nums1), m = len(nums2)).

Time

O(n + m)

Space

O(m)

Pitfall

The answer is the nearest larger value to the right, not the largest one: for 1 in nums2 = [1,3,4,2] it's 3, not 4. Also search to the right of x's position in nums2, not its position in nums1.

Solutions

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nxt = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int num : nums2) {
            while (!stack.isEmpty() && stack.peek() < num) {
                nxt.put(stack.pop(), num);
            }
            stack.push(num);
        }
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = nxt.getOrDefault(nums1[i], -1);
        }
        return result;
    }
}
Drill This