Next Greater Element I

How it works

A monotonic stack solves this problem in linear time. We iterate through nums2 and maintain a stack of elements that have not yet found their next greater element. When we encounter a larger element, it becomes the "next greater" for all smaller elements on the stack.

The stack maintains decreasing order from bottom to top. When a new element is larger than the stack top, we pop elements and record the current element as their next greater. We only push elements that are in nums1 since those are the only ones we need answers for.

Steps

1. Build a hash map that maps each element in nums1 to its index.
2. Initialize result array with all -1 values.
3. Iterate through nums2 with a stack:
   • While the stack is not empty and the current element is greater than the stack top:
     • Pop the top, find its index in nums1, and set result[index] to current element.
   • If current element is in nums1, push it onto the stack.
4. Return the result array.

Complexity

• Time complexity: O(m + n)
• Space complexity: O(m)

Where m is the size of the array nums1 and n is the size of the array nums2.

Things to watch for

Searching in Wrong Array

The next greater element must be found in nums2, to the right of where the element appears in nums2. Some solutions mistakenly look for the next greater element within nums1 or search to the left instead of right in nums2.

Pushing All Elements onto Stack

The stack optimization only needs to track elements from nums1 that are waiting for their next greater element. Pushing every element from nums2 onto the stack works but uses unnecessary space. Only push elements that exist in the nums1 lookup map.

from typing import List

class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1Idx = {num : i for i, num in enumerate(nums1)}
        res = [-1] * len(nums1)

        stack = []
        for i in range(len(nums2)):
            cur = nums2[i]
            while stack and cur > stack[-1]:
                val = stack.pop()
                idx = nums1Idx[val]
                res[idx] = cur
            if cur in nums1Idx:
                stack.append(cur)
        return res

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> nums1Idx;
        for (int i = 0; i < nums1.size(); i++) {
            nums1Idx[nums1[i]] = i;
        }

        vector<int> res(nums1.size(), -1);
        stack<int> stack;

        for (int num : nums2) {
            while (!stack.empty() && num > stack.top()) {
                int val = stack.top();
                stack.pop();
                int idx = nums1Idx[val];
                res[idx] = num;
            }
            if (nums1Idx.find(num) != nums1Idx.end()) {
                stack.push(num);
            }
        }
        return res;
    }
};