# Next Greater Element I
**Difficulty:** EASY
[External](https://leetcode.com/problems/next-greater-element-i)
Canonical: https://scaleengineer.com/dsa/problems/next-greater-element-i
**Data structures:** Array, Hash Table, Stack, Monotonic Stack
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Agoda](https://scaleengineer.com/companies/agoda), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Swiggy](https://scaleengineer.com/companies/swiggy), [Tencent](https://scaleengineer.com/companies/tencent)
---
## Problem
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.

You are given two **distinct 0-indexed** integer arrays `nums1` and `nums2`, where `nums1` is a subset of `nums2`.

For each `0 <= i < nums1.length`, find the index `j` such that `nums1[i] == nums2[j]` and determine the **next greater element** of `nums2[j]` in `nums2`. If there is no next greater element, then the answer for this query is `-1`.

Return _an array_ `ans` _of length_ `nums1.length` _such that_ `ans[i]` _is the **next greater element** as described above._

**Example 1:**

**Input:** nums1 = [4,1,2], nums2 = [1,3,4,2]
**Output:** [-1,3,-1]
**Explanation:** The next greater element for each value of nums1 is as follows:
- 4 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.
- 1 is underlined in nums2 = [1,3,4,2]. The next greater element is 3.
- 2 is underlined in nums2 = [1,3,4,2]. There is no next greater element, so the answer is -1.

**Example 2:**

**Input:** nums1 = [2,4], nums2 = [1,2,3,4]
**Output:** [3,-1]
**Explanation:** The next greater element for each value of nums1 is as follows:
- 2 is underlined in nums2 = [1,2,3,4]. The next greater element is 3.
- 4 is underlined in nums2 = [1,2,3,4]. There is no next greater element, so the answer is -1.

**Constraints:**

* `1 <= nums1.length <= nums2.length <= 1000`
* `0 <= nums1[i], nums2[i] <= 104`
* All integers in `nums1` and `nums2` are **unique**.
* All the integers of `nums1` also appear in `nums2`.

**Follow up:** Could you find an `O(nums1.length + nums2.length)` solution?

# Approaches
## Brute Force using Nested Loops
This is the most straightforward, brute-force approach. For each element in `nums1`, we iterate through `nums2` to find that element's position. Then, we perform another iteration from that position onwards in `nums2` to find the first element that is greater. This involves nested loops, leading to a quadratic time complexity.
**Time:** O(m * n), where m is the length of `nums1` and n is the length of `nums2`. For each of the `m` elements in `nums1`, we may have to scan the entire `nums2` array twice in the worst case. · **Space:** O(m), where m is the length of `nums1`. This space is used for the result array. If the output array is not considered extra space, the complexity is O(1).
**Pros:** Simple to understand and implement.; Requires minimal extra space (only for the output array).
**Cons:** Highly inefficient for large input arrays, with a quadratic time complexity.; Likely to result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for larger constraints.
### Explanation
This method directly translates the problem statement into code. For every element in `nums1`, we find it in `nums2` and then scan the rest of `nums2` to find the first element that is larger.

*   **Algorithm:**
    1.  Initialize an integer array `result` of the same size as `nums1` to store the answers.
    2.  Iterate through each element `num1` at index `i` in the `nums1` array.
    3.  For each `num1`, find its index in the `nums2` array. Let's call this `foundIndex`.
    4.  Once `num1` is found at `foundIndex` in `nums2`, start another search from `foundIndex + 1` to the end of `nums2`.
    5.  The first element `nums2[k]` (where `k > foundIndex`) that is greater than `num1` is the next greater element.
    6.  Store this element in `result[i]` and break the inner search.
    7.  If the inner search completes without finding any greater element, it means no such element exists. In this case, store `-1` in `result[i]`.
    8.  After iterating through all elements of `nums1`, return the `result` array.

```java
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            int currentNum = nums1[i];
            int foundIndex = -1;
            // Find the index of currentNum in nums2
            for (int j = 0; j < nums2.length; j++) {
                if (nums2[j] == currentNum) {
                    foundIndex = j;
                    break;
                }
            }

            // Search for the next greater element from foundIndex + 1
            int nextGreater = -1;
            for (int k = foundIndex + 1; k < nums2.length; k++) {
                if (nums2[k] > currentNum) {
                    nextGreater = nums2[k];
                    break;
                }
            }
            result[i] = nextGreater;
        }
        return result;
    }
}
```
### Algorithm
*   Initialize an integer array `result` of the same size as `nums1` to store the answers.
*   Iterate through each element `num1` at index `i` in the `nums1` array.
*   For each `num1`, find its index in the `nums2` array. Let's call this `foundIndex`.
*   Once `num1` is found at `foundIndex` in `nums2`, start another search from `foundIndex + 1` to the end of `nums2`.
*   The first element `nums2[k]` (where `k > foundIndex`) that is greater than `num1` is the next greater element.
*   Store this element in `result[i]` and break the inner search.
*   If the inner search completes without finding any greater element, it means no such element exists. In this case, store `-1` in `result[i]`.
*   After iterating through all elements of `nums1`, return the `result` array.

## Optimal Approach using Monotonic Stack and HashMap
This is an optimal approach that achieves linear time complexity. The key idea is to pre-compute the next greater element for all numbers in `nums2` in a single pass. This is done efficiently using a monotonic stack (a stack that maintains a specific order, in this case, decreasing). The results are stored in a hash map, allowing for O(1) lookups when processing `nums1`.
**Time:** O(n + m), where n is the length of `nums2` and m is the length of `nums1`. We iterate through `nums2` once (O(n)) and `nums1` once (O(m)). Each element of `nums2` is pushed and popped from the stack at most once, making the stack operations amortize to O(n) in total. · **Space:** O(n + m), where n is the length of `nums2` and m is the length of `nums1`. In the worst case (e.g., a strictly decreasing `nums2`), the `nextGreaterMap` and the `stack` can store up to `n` elements. The result array requires O(m) space.
**Pros:** Highly efficient with a linear time complexity, satisfying the follow-up question.; Scales well for large inputs.
**Cons:** More complex to understand and implement compared to the brute-force approach.; Requires additional space for the hash map and the stack.
### Explanation
This optimized approach avoids the repeated scans of `nums2`. The core idea is to pre-calculate the next greater element for every number in `nums2` in a single pass. This is achieved using a monotonic stack, which stores elements in a strictly decreasing order.

*   **Algorithm:**
    1.  Create a `HashMap` called `nextGreaterMap` to store the mapping from an element to its next greater element.
    2.  Create an empty `Stack` of integers. This will be our monotonic stack.
    3.  Iterate through the `nums2` array from left to right. For each number `num`:
        a.  While the stack is not empty and the current `num` is greater than the element at the top of the stack (`stack.peek()`), it means we have found the next greater element for `stack.peek()`.
        b.  Pop the element from the stack and put the pair (`stack.pop()`, `num`) into `nextGreaterMap`.
        c.  Repeat this until the stack is empty or `num <= stack.peek()`.
        d.  Push the current `num` onto the stack. This maintains the stack's property of having elements in decreasing order from bottom to top.
    4.  After the loop, any elements remaining in the stack do not have a next greater element, so their answer is -1.
    5.  Create a `result` array of the same size as `nums1`.
    6.  Iterate through `nums1`. For each element `num1`, find its next greater element from `nextGreaterMap`. If it's not in the map, the default value is -1.
    7.  Store the found value in the `result` array.
    8.  Return the `result` array.

*   **Example Walkthrough (`nums2 = [1,3,4,2]`):**
    -   `num = 1`: Stack is empty, push 1. `stack: [1]`
    -   `num = 3`: `3 > stack.peek() (1)`. Pop 1, `map.put(1, 3)`. Stack is empty. Push 3. `stack: [3]`
    -   `num = 4`: `4 > stack.peek() (3)`. Pop 3, `map.put(3, 4)`. Stack is empty. Push 4. `stack: [4]`
    -   `num = 2`: `2 < stack.peek() (4)`. Push 2. `stack: [4, 2]`
    -   End of loop. `map` is `{1: 3, 3: 4}`.
    -   Now, for `nums1 = [4,1,2]`, we query the map: `map.getOrDefault(4, -1) -> -1`, `map.getOrDefault(1, -1) -> 3`, `map.getOrDefault(2, -1) -> -1`.

```java
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

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

        // Pre-compute next greater elements for all numbers in nums2
        for (int num : nums2) {
            while (!stack.isEmpty() && num > stack.peek()) {
                nextGreaterMap.put(stack.pop(), num);
            }
            stack.push(num);
        }

        // Build the result array using the pre-computed map
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = nextGreaterMap.getOrDefault(nums1[i], -1);
        }

        return result;
    }
}
```
### Algorithm
*   Create a `HashMap` called `nextGreaterMap` to store the mapping from an element to its next greater element.
*   Create an empty `Stack` of integers. This will be our monotonic stack.
*   Iterate through the `nums2` array from left to right. For each number `num`:
    a.  While the stack is not empty and the current `num` is greater than the element at the top of the stack (`stack.peek()`), it means we have found the next greater element for `stack.peek()`.
    b.  Pop the element from the stack and put the pair (`stack.pop()`, `num`) into `nextGreaterMap`.
    c.  Repeat this until the stack is empty or `num <= stack.peek()`.
    d.  Push the current `num` onto the stack. This maintains the stack's property of having elements in decreasing order from bottom to top.
*   After the loop, any elements remaining in the stack do not have a next greater element, so their answer is -1.
*   Create a `result` array of the same size as `nums1`.
*   Iterate through `nums1`. For each element `num1`, find its next greater element from `nextGreaterMap`. If it's not in the map, the default value is -1.
*   Store the found value in the `result` array.
*   Return the `result` array.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var nextGreaterElement =
  function (nums1, nums2) {
    let stk = [];
    let m = {};
    for (let v of nums2) {
      while (stk && stk[stk.length - 1] < v) {
        m[stk.pop()] = v;
      }
      stk.push(v);
    }
    return nums1.map((e) => m[e] || -1);
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2) {
    stack<int> stk;
    unordered_map<int, int> m;
    for (int &v : nums2) {
      while (!stk.empty() && stk.top() < v) {
        m[stk.top()] = v;
        stk.pop();
      }
      stk.push(v);
    }
    vector<int> ans;
    for (int &v : nums1)
      ans.push_back(m.count(v) ? m[v] : -1);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]: m = {} stk = [] for v in nums2: while stk and stk[- 1] < v: m[stk . pop()] = v stk . append(v) return [m . get(v, - 1) for v in nums1]

```