# 0041. First Missing Positive

Hard Array Sort## Problem

Hard U:3696 D:813

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

- Example 1:

```
Input: [1,2,0]
Output: 3
```

- Example 2:

```
Input: [3,4,-1,1]
Output: 2
```

- Example 3:

```
Input: [7,8,9,11,12]
Output: 1
Follow up:
```

NOTE: **Your algorithm should run in O(n) time and uses constant extra space.**

## Problem Insights

At first, we may came up with an idea to sort the array, then loop through to
find the missing positive. However, as the NOTE mentioned, it’s obviously
impossible to run in `O(n)`

time and `O(1)`

space if we’re going to sort the array.
Because, for whom familiar with the sort algorithms, the best sort time at least
take `O(log n)`

time.

Other ideas may came up with HashTable etc…but also impossible to keep an
`O(1)`

space.

Let’s take a look at the example 2 `[3,4,-1,1]`

and example 3 `[7,8,9,11,12]`

,

Imaging there are no missing positive, then example 2 should be `[1, 2, 3, 4]`

,
and example 3 should be `[1, 2, 3, 4, 5]`

.

Considering the positives, in conclusion, for any `nums`

with length `nlen`

, the
first missing positive must be within `1-nlen`

.

To find the missing positive, first of all we can ignore the `0`

and
`non-positive`

values, then the values which are greater than `nlen`

are
also useless.

First idea, we may think about **how to put the right number to the right index**.
which for example 2, if by some way to **swap** the items to array like this:
`[1, x, 3, 4]`

(ignore negative `-1`

), then it’s not hard to iterate and find
the missing positive is `2`

. (-> See Solution Ⅰ)

The second idea is, if we can use each index of numbers as a hash to record the
“frequency” of each number, then by iterate the array, the **zero frequency**
number is the missing one. (-> See Solution Ⅱ)

This idea comes from: @asones post

## Solutions

### Solution Ⅰ

```
func firstMissingPositive2(nums []int) int {
for i := 0; i < len(nums); i++ {
for nums[i] > 0 && nums[i] < len(nums) && nums[nums[i]-1] != nums[i] {
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
}
}
for i := 0; i < len(nums); i++ {
if nums[i] != i+1 {
return i + 1
}
}
return len(nums) + 1
}
```

### Solution Ⅱ

```
func firstMissingPositive3(nums []int) int {
nums = append(nums, 0)
nlen := len(nums)
// Reset those useless elements
for i, n := range nums {
if n < 0 || n >= nlen {
nums[i] = 0
}
}
//
for i := range nums {
nums[nums[i]%nlen] += nlen
}
for i := 1; i < nlen; i++ {
if nums[i]/nlen == 0 {
return i
}
}
return nlen
}
```