> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/stack/next-greater-element-i.md).

# Next Greater Element I

## Question ([LC.496](https://leetcode.com/problems/next-greater-element-i/description/))

> 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 

```java
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.&#x20;

## Monotonic Stack Approach&#x20;

A classic example&#x20;

Push to a min stack&#x20;

* elements in stack do not have a greater element yet &#x20;

Pop when the current element is bigger&#x20;

* all the elements in stack smaller than the current element has a next greater element now&#x20;

## Code&#x20;

```java
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)&#x20;

Space O(n2)