# LeetCode 496: Next Greater Element I

## Problem Restatement

We are given two arrays:

| Array | Meaning |
|---|---|
| `nums1` | Query numbers |
| `nums2` | A larger reference array |

Every value in both arrays is unique, and every value in `nums1` appears in `nums2`.

For each value `x` in `nums1`, we need to find the first greater number appearing to the right of `x` inside `nums2`.

If no greater value exists, return `-1` for that number.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Arrays `nums1` and `nums2` |
| Output | Array of next greater values |
| Uniqueness | All elements are unique |
| Relation | `nums1` is a subset of `nums2` |

Function shape:

```python
def nextGreaterElement(
    nums1: list[int],
    nums2: list[int],
) -> list[int]:
    ...
```

## Examples

Example 1:

```python
nums1 = [4, 1, 2]
nums2 = [1, 3, 4, 2]
```

For `4`:

```text
No greater value exists to its right.
```

Answer for `4`:

```python
-1
```

For `1`:

```text
The first greater value to the right is 3.
```

Answer for `1`:

```python
3
```

For `2`:

```text
No greater value exists.
```

Answer for `2`:

```python
-1
```

Final result:

```python
[-1, 3, -1]
```

Example 2:

```python
nums1 = [2, 4]
nums2 = [1, 2, 3, 4]
```

For `2`, the next greater value is `3`.

For `4`, no greater value exists.

Answer:

```python
[3, -1]
```

## First Thought: Scan to the Right

For every value in `nums1`:

1. Find its position in `nums2`.
2. Scan rightward until finding a larger number.

```python
class Solution:
    def nextGreaterElement(
        self,
        nums1: list[int],
        nums2: list[int],
    ) -> list[int]:
        ans = []

        for x in nums1:
            idx = nums2.index(x)

            next_greater = -1

            for j in range(idx + 1, len(nums2)):
                if nums2[j] > x:
                    next_greater = nums2[j]
                    break

            ans.append(next_greater)

        return ans
```

This works, but repeated scanning is inefficient.

## Problem With Brute Force

For each query number, we may scan most of `nums2`.

If:

```text
len(nums1) = m
len(nums2) = n
```

then the worst-case time complexity is:

```text
O(m * n)
```

We can preprocess `nums2` once so every query becomes fast.

## Key Insight

We need the next greater element to the right.

This is a classic monotonic stack problem.

Process `nums2` from left to right.

Maintain a stack that is strictly decreasing.

For example:

```text
stack top is the most recent unresolved smaller number
```

When we see a new number `num`:

| Case | Meaning |
|---|---|
| `num` is smaller | Push it onto the stack |
| `num` is larger | It becomes the next greater element for smaller stack values |

So while:

```python
stack[-1] < num
```

we pop from the stack and record:

```python
next_greater[popped] = num
```

At the end, remaining stack values have no greater element, so they map to `-1`.

## Example Walkthrough

Consider:

```python
nums2 = [1, 3, 4, 2]
```

### Step 1

Current value:

```text
1
```

Stack:

```text
[1]
```

### Step 2

Current value:

```text
3
```

Since:

```text
3 > 1
```

we pop `1` and record:

```text
1 -> 3
```

Stack becomes:

```text
[3]
```

### Step 3

Current value:

```text
4
```

Since:

```text
4 > 3
```

record:

```text
3 -> 4
```

Stack becomes:

```text
[4]
```

### Step 4

Current value:

```text
2
```

Since:

```text
2 < 4
```

push it.

Final unresolved stack:

```text
[4, 2]
```

These values have no next greater element.

## Algorithm

1. Create:
   - a decreasing stack
   - a hash map `next_greater`
2. Scan `nums2`.
3. While the current number is greater than the stack top:
   - pop the stack
   - record the current number as its next greater value
4. Push the current number.
5. Build the final answer for `nums1` using the map.
6. Missing values return `-1`.

## Correctness

The stack is maintained in strictly decreasing order.

When processing a value `num`, every smaller value on top of the stack cannot find a closer greater element than `num`, because:

1. They were pushed earlier.
2. All values between them and `num` were smaller than or equal to them, otherwise they would already have been popped.

Therefore, when `num` pops a value `x`, `num` is exactly the first greater value to the right of `x`.

Every value is pushed once and popped at most once. So every value either:

| Case | Result |
|---|---|
| Gets popped | Its next greater value is recorded |
| Remains in stack | No greater value exists to its right |

Thus the map correctly stores the next greater element for every number in `nums2`.

Finally, since every number in `nums1` appears in `nums2`, looking up the map gives the correct answer for each query.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + m)` | Each number is pushed and popped at most once |
| Space | `O(n)` | Stack and hash map store values from `nums2` |

Here:

| Symbol | Meaning |
|---|---|
| `n` | `len(nums2)` |
| `m` | `len(nums1)` |

## Implementation

```python
class Solution:
    def nextGreaterElement(
        self,
        nums1: list[int],
        nums2: list[int],
    ) -> list[int]:
        stack = []
        next_greater = {}

        for num in nums2:
            while stack and stack[-1] < num:
                smaller = stack.pop()
                next_greater[smaller] = num

            stack.append(num)

        return [
            next_greater.get(num, -1)
            for num in nums1
        ]
```

## Code Explanation

The stack stores unresolved values:

```python
stack = []
```

The hash map stores answers:

```python
next_greater = {}
```

As we scan `nums2`:

```python
for num in nums2:
```

we resolve all smaller stack values:

```python
while stack and stack[-1] < num:
```

The current number becomes their next greater value:

```python
smaller = stack.pop()
next_greater[smaller] = num
```

Then the current number waits for its own next greater value:

```python
stack.append(num)
```

Finally, build answers for `nums1`:

```python
return [
    next_greater.get(num, -1)
    for num in nums1
]
```

If a number was never resolved, its answer is `-1`.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.nextGreaterElement(
        [4, 1, 2],
        [1, 3, 4, 2],
    ) == [-1, 3, -1]

    assert s.nextGreaterElement(
        [2, 4],
        [1, 2, 3, 4],
    ) == [3, -1]

    assert s.nextGreaterElement(
        [1],
        [1],
    ) == [-1]

    assert s.nextGreaterElement(
        [1, 3],
        [3, 1, 4],
    ) == [4, 4]

    assert s.nextGreaterElement(
        [2],
        [2, 1, 3],
    ) == [3]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[4,1,2]` example | Mixed answers |
| `[2,4]` example | One success and one failure |
| Single value | No greater element exists |
| `[3,1,4]` | Multiple values share the same next greater |
| `[2,1,3]` | Greater element appears later after smaller values |