Problems

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.