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.