📊Next Greater Element I

Question (LC.496)

Two integer arrays nums1 and nums2 are given as input. nums2 is the main array. nums1 is a subset of nums2. Find all the next greater elements for each element in nums1

Example

Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]

Initial Approach

For each element in nums1 find it in nums2 and find the element greater than itself

O(n1 * n2)

Code

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    int[] results = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        results[i] = nextGreaterHelper(nums1[i], nums2);
    }
    return results;
}

private int nextGreaterHelper(int element, int[] nums) {
    // if element is not in nums or does not have a greater element 
    // return -1 
    if (nums == null || nums.length == 0) {
        return -1;
    }

    int eleIndex = -1;
    for (int i = 0; i < nums.length; i++) {
        if (element == nums[i]) {
            eleIndex = i;
            break;
        }
    }

    if (eleIndex == -1) {
        return -1;
    }

    for (int i = eleIndex + 1; i < nums.length; i++) {
        if (nums[i] > element) {
            return nums[i];
        }
    }

    return -1;
}

Test cases are easy for this question. The run time is 2ms and beats 98% of the solutions.

Monotonic Stack Approach

A classic example

Push to a min stack

• elements in stack do not have a greater element yet

Pop when the current element is bigger

• all the elements in stack smaller than the current element has a next greater element now

Code

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    // look up index by value 
    Map<Integer, Integer> valToIndex = new HashMap<>();
    for (int i = 0; i < nums2.length; i++) {
        valToIndex.put(nums2[i], i);
    }

    // right bounds 
    int[] rightBounds = new int[nums2.length];
    for (int i = 0; i < rightBounds.length; i++) {
        rightBounds[i] = -1;
    }

    // store index in stack
    Stack<Integer> minStack = new Stack<>();
    for (int i = 0; i < nums2.length; i++) {
        // pop
        while (!minStack.isEmpty() && nums2[minStack.peek().intValue()] < nums2[i]) {
            // nums2[i] is the next greater element to the element in stack
            int popIndex = minStack.pop().intValue();
            rightBounds[popIndex] = nums2[i];
        }
        minStack.push(i);
    }

    int[] results = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        int lookupIndex = valToIndex.get(nums1[i]);
        results[i] = rightBounds[lookupIndex];
    }
    return results;
}

Time O(n1 + n2)

Space O(n2)