# First Missing Positive

## Problem

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

### Example

Given `[1,2,0]`

return `3`

,

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

return `2`

.

### Challenge

Your algorithm should run in `O(n)`

time and uses constant space.

## Solution

The most straightforward solution is to sort the array, but the time complexity would be `O(n log n)`

.

### Solution 1

Assume the array length is `n`

, any positive number `i`

equal or less than `n`

can be placed in the array at `i - 1`

, so if we check each number `num[i]`

in the array, if `0 < num[i] <= n`

, we keep swapping the number to it's position, otherwise we ignore this out-of-range number. Then from the beginning, find that first `i`

that `num[i] != i + 1`

.

(Check the Java solution below.)

### Solution 2

First convert all non-positive numbers to `n + 1`

so that they are still out-of-range, but all the numbers in the array are positive now, and we can use the sign of the number to denote whether the number exists.

Then for each `num[i]`

, if it is within range (`0 < num[i] <= n`

), then set `num[num[i] - 1]`

to negaive. After that, if `num[k]`

is negative, `k`

must have appeared in the values of the array, so we can simply return `k + 1`

(`k`

is the index, starting from `0`

) of the first positive `num[k]`

we meet. If we cannot find such `k`

, all positive numbers are in the array, so return `n + 1`

instead.

(Check the Go solution below.)

## Language Specific Notes

### Go

There's no `Abs()`

function for `int`

(only for `float64`

). You need to handle the absolute numbers on your own.