Reference: LeetCode

Difficulty: Hard

## Problem

Given an unsorted integer array, find the smallest missing positive integer.

**Example:**

1 | Input: [1,2,0] |

**Follow up:** Your algorithm should run in $O(n)$ time and uses `constant extra space`

.

## Analysis

**Basic Idea:** Since there are only `n`

spaces in the array, we have the follow different cases (`n = 5`

):

`[1, 2, 3, 4, 5]`

: Return`6`

. (`n + 1`

)`[1, 2, 2, 4, 5]`

: Return`3`

. (`[1, n]`

)`[1, 2, -1, 2, 5]`

: Return`3`

. (`[1, n]`

)

The invariant is that the smallest positive integer must be in the interval `[1, n + 1]`

.

### Brute-Force

For each value in `[1, n]`

, check if it is in `nums`

.

- If it does not exist, return the corresponding index
`i`

. - If all values in
`[1, n]`

exist in the array, return`n + 1`

.

1 | public int firstMissingPositive(int[] nums) { |

**Time:** $O(N^2)$**Space:** $O(1)$

### Hash Set

The brute-force approach could be optimized by using a hash set.

1 | public int firstMissingPositive(int[] nums) { |

**Time:** $O(N)$**Space:** $O(N)$

### In-place Optimization

We can actually use the values in the array to indicate if the values from `1`

to `n`

exists.

1 | Input: [3, 4, -1, 1] |

For example, since `3`

exists, we set the value (`-1`

) at `3 - 1`

to negative.

Before this process, we should traverse the array, setting all non-positive numbers and out-of-bound numbers to `1`

. In the above example, the output of preprocessing will be `[3, 4, 1, 1]`

.

Since we set those values to `1`

, during the first iteration, we must check if `1`

exists. If it does not exist, the result is going to be `1`

. No further action should be made.

Then we process the array `[3, 4, 1, 1]`

, the output is `[-3, 4, -1, -1]`

. In the final pass, we find that `4`

is positive. So the element is the index of `4`

plus one, which is `2`

.

**Note:** When using `val`

as index, remember to use the absolute value because it might be set to negative in advance.

1 | public int firstMissingPositive(int[] nums) { |

**Time:** $O(N)$**Space:** $O(1)$