leetcode: First Missing Positive

Problem Description:

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

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

Solution and Precautions:

Linear time usually requires hash table to do search in constant time, constant space requires we use a fixed number of variables or we directly use the input memory. Here constant space means the second case. So basically we use the input array A[] as our hash table, and by one pass through the whole array, we put each number a >= 1 and a <= n into the right position, that is a should be in position a-1, the key observation is that, the first missing positive could only be 1,….n, n+1, so basically we try to set all these positions in A to contain the right number, after this is done, we check the first slot where the position does not contain the right number, this position + 1 is the first missing positive. We can use swap or something else to do the thing that we set the position to contain the right number.

Written on June 5, 2013