# LeetCode 41: First Missing Positive

## Problem Restatement

We are given an unsorted integer array `nums`.

We need to return the smallest positive integer that does not appear in the array.

The solution must run in `O(n)` time and use `O(1)` auxiliary space.

Examples:

```python
nums = [1, 2, 0]
```

The positive integers `1` and `2` are present, so the smallest missing positive integer is `3`.

```python
nums = [3, 4, -1, 1]
```

The number `1` is present, but `2` is missing, so the answer is `2`.

```python
nums = [7, 8, 9, 11, 12]
```

The number `1` is missing, so the answer is `1`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An unsorted integer array `nums` |
| Output | The smallest positive integer not present in `nums` |
| Constraint | Must use `O(n)` time |
| Constraint | Must use `O(1)` auxiliary space |

The function shape is:

```python
def firstMissingPositive(nums: list[int]) -> int:
    ...
```

## Key Observation

Let `n = len(nums)`.

The answer must be in the range:

```python
1, 2, 3, ..., n + 1
```

Why?

If the array contains every number from `1` to `n`, then the smallest missing positive is `n + 1`.

Otherwise, at least one number from `1` to `n` is missing, and the smallest missing positive is inside that range.

So we only care about values from `1` to `n`.

Values like `0`, negative numbers, and numbers greater than `n` cannot be the smallest missing positive.

## First Thought: Use a Set

A simple solution is to put all numbers into a set.

Then check `1`, `2`, `3`, and so on until we find the first number not in the set.

```python
class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        seen = set(nums)

        x = 1
        while x in seen:
            x += 1

        return x
```

This is easy to understand.

The problem is space.

The set may store `n` numbers, so the space complexity is `O(n)`. The problem asks for `O(1)` auxiliary space, so we need to use the input array itself.

## Key Insight

For a number `x` in the range `1 <= x <= n`, its natural position is index `x - 1`.

So:

| Number | Correct Index |
|---|---|
| `1` | `0` |
| `2` | `1` |
| `3` | `2` |
| `x` | `x - 1` |

We can rearrange the array in-place so that every useful number goes to its correct index.

After rearranging, if index `i` does not contain `i + 1`, then `i + 1` is missing.

For example:

```python
nums = [3, 4, -1, 1]
```

After placing valid numbers in their correct positions, we want something like:

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

Index `0` has `1`.

Index `1` should have `2`, but it does not.

So the answer is `2`.

## Algorithm

Let `n = len(nums)`.

First pass: rearrange the array.

For each index `i`, while `nums[i]` is a useful number and is not already in the correct place, swap it into its correct place.

A number is useful if:

```python
1 <= nums[i] <= n
```

Its correct index is:

```python
nums[i] - 1
```

We keep swapping while:

```python
1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]
```

The second condition prevents infinite loops with duplicates.

For example, in:

```python
nums = [1, 1]
```

The second `1` wants to go to index `0`, but index `0` already contains `1`. There is nothing useful to swap.

Second pass: find the first mismatch.

For each index `i`, if:

```python
nums[i] != i + 1
```

then `i + 1` is the smallest missing positive.

If every index is correct, return:

```python
n + 1
```

## Walkthrough

Use this input:

```python
nums = [3, 4, -1, 1]
```

The length is `4`, so we only care about numbers from `1` to `4`.

Start:

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

At index `0`, the value is `3`.

The correct index for `3` is `2`.

Swap index `0` and index `2`:

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

Now index `0` has `-1`, which is not useful.

At index `1`, the value is `4`.

The correct index for `4` is `3`.

Swap index `1` and index `3`:

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

Index `1` now has `1`.

The correct index for `1` is `0`.

Swap index `1` and index `0`:

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

Now the array has useful numbers in their correct places where possible.

Scan from left to right:

| Index | Expected | Actual |
|---|---:|---:|
| `0` | `1` | `1` |
| `1` | `2` | `-1` |

The first mismatch is at index `1`.

So the answer is:

```python
2
```

## Correctness

Every positive integer `x` in the range `1 <= x <= n` has exactly one correct position: index `x - 1`.

During the first pass, whenever such a number is not already represented at its correct position, we swap it closer to that position. The swap places `x` at index `x - 1`.

Duplicates are handled by the condition:

```python
nums[i] != nums[nums[i] - 1]
```

If the correct position already contains the same value, then placing another copy there would not help. We stop swapping that value.

After the first pass, if a number `x` from `1` to `n` exists in the array, then one copy of `x` must be at index `x - 1`.

Therefore, during the second pass, the first index `i` where `nums[i] != i + 1` means the value `i + 1` is not present in the array.

Because we scan indices from left to right, this is the smallest missing positive integer.

If every index `i` contains `i + 1`, then all numbers from `1` to `n` are present. The smallest missing positive integer is therefore `n + 1`.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each useful value is moved into its correct position at most once |
| Space | `O(1)` | The array is rearranged in-place |

Although the code has a nested `while` loop, the total number of swaps is bounded by `O(n)`. Each successful swap places at least one useful number into its final position.

## Implementation

```python
class Solution:
    def firstMissingPositive(self, nums: list[int]) -> int:
        n = len(nums)

        for i in range(n):
            while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
                correct_index = nums[i] - 1
                nums[i], nums[correct_index] = nums[correct_index], nums[i]

        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        return n + 1
```

## Code Explanation

We first store the array length:

```python
n = len(nums)
```

Only values from `1` to `n` matter.

Then we scan every index:

```python
for i in range(n):
```

At each index, we keep moving the current value while it is useful and not already represented at its correct position:

```python
while 1 <= nums[i] <= n and nums[i] != nums[nums[i] - 1]:
```

The correct index for `nums[i]` is:

```python
correct_index = nums[i] - 1
```

Then we swap:

```python
nums[i], nums[correct_index] = nums[correct_index], nums[i]
```

After this rearrangement, we scan the array again:

```python
for i in range(n):
    if nums[i] != i + 1:
        return i + 1
```

The first mismatch gives the smallest missing positive.

If there is no mismatch, the array contains all values from `1` to `n`, so the answer is:

```python
return n + 1
```

## Testing

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

    assert s.firstMissingPositive([1, 2, 0]) == 3
    assert s.firstMissingPositive([3, 4, -1, 1]) == 2
    assert s.firstMissingPositive([7, 8, 9, 11, 12]) == 1
    assert s.firstMissingPositive([1]) == 2
    assert s.firstMissingPositive([2]) == 1
    assert s.firstMissingPositive([1, 1]) == 2
    assert s.firstMissingPositive([2, 2]) == 1
    assert s.firstMissingPositive([1, 2, 3, 4]) == 5
    assert s.firstMissingPositive([-1, -2, 0]) == 1
    assert s.firstMissingPositive([2, 1]) == 3

    print("all tests passed")

run_tests()
```

| Test | Expected | Reason |
|---|---:|---|
| `[1, 2, 0]` | `3` | `1` and `2` are present |
| `[3, 4, -1, 1]` | `2` | `1` is present, `2` is missing |
| `[7, 8, 9, 11, 12]` | `1` | No useful small positive appears |
| `[1]` | `2` | `1` is present |
| `[2]` | `1` | `1` is missing |
| `[1, 1]` | `2` | Duplicate `1` |
| `[1, 2, 3, 4]` | `5` | All values from `1` to `n` are present |