Problem: Next Greater Element I

Problem Statement

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

Given two arrays nums1 and nums2, find the next greater element for each nums1[i] in nums2.

Approach: Monotonic Stack

A brute force $O(n^2)$ approach would check every element to the right. To achieve $O(n)$, we use a Monotonic Decreasing Stack.

Initialize: A stack to store elements whose "Next Greater" hasn't been found, and a Map to store results.
Iterate nums2:
- While the stack is not empty and current element > stack.peek():
  - The current element is the "Next Greater" for the top element.
  - Map stack.pop() -> current.
- Push current onto stack.
Result: Build the output for nums1 using the Map.

Java Implementation

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Stack<Integer> stack = new Stack<>();
    Map<Integer, Integer> map = new HashMap<>();

    for (int num : nums2) {
        while (!stack.isEmpty() && stack.peek() < num) {
            map.put(stack.pop(), num);
        }
        stack.push(num);
    }

    int[] res = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        res[i] = map.getOrDefault(nums1[i], -1);
    }
    return res;
}

Complexity Analysis

Time Complexity: $O(n + m)$. Every element is pushed and popped at most once.
Space Complexity: $O(n + m)$ for the map and stack.

Interview Tips