Lintcode: First Missing Positive

Given an unsorted integer array, find the first missingpositive integer.

Have you met this question in a real interview? 

Yes

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.

Tags Expand 

Array

Initial thoughts:
Get the max integer in the array and store values in an hashmap at the same time. O(n)
Then check whether number from 1 to the max integer exist, the first one that doesn't exist is what we are looking for. O(n)
Time: O(n)
Space: O(n)

class Solution {
public:
    /**    
     * @param A: a vector of integers
     * @return: an integer
     */
    int firstMissingPositive(vector<int> A) {
        // write your code here
        unordered_set<int> hashmap;
        int max = 0;
        for(int i = 0; i < A.size(); i++){
            if(A[i] > max) max = A[i];
            if(A[i] > 0 && !hashmap.count(A[i])) hashmap.insert(A[i]);
        }
        for(int i = 1; i <= max; i++){
            if(!hashmap.count(i)) return i;
        }
        return max + 1;
    }
};

However, this is not a constant space.

Optimized solution: Bucket Sort 
Definition of bucket sort
Solution reference:
http://www.programcreek.com/2014/05/leetcode-first-missing-positive-java/
http://bangbingsyb.blogspot.com/2014/11/leetcode-first-missing-positive.html
http://algorithm.yuanbin.me/integer_array/first_missing_positive.html
Assume input is A[n]
The first missing positive has to be in the index range of input.
So we don't need to care about those numbers that is negative or more than length of array.
Just put numbers in the range of (1, n) into corresponding array position.
Then the position of the first element which is not continuous with others is the first missing positive.
Time: O(n)
Space: O(1)

class Solution {
public:
    /**    
     * @param A: a vector of integers
     * @return: an integer
     */
    int firstMissingPositive(vector<int> A) {
        // write your code here
        int n = A.size();
        for(int i = 0; i < A.size(); i++){
            while(A[i] != i + 1 && A[i] > 0 && A[i] <= n){
                if(A[i] == A[A[i] - 1]) break;//avoid endless loop
                int temp = A[A[i] - 1];
                A[A[i] - 1] = A[i];
                A[i] = temp;
            }
        }
        for(int i = 0; i < A.size(); i++){
            if(A[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
};

second Lintcode:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { public: /** * @param A: a vector of integers * @return: an integer */ int firstMissingPositive(vector<int> A) { // write your code here unordered_set<int> hashset; for(int i = 0; i < A.size(); i++){ hashset.insert(A[i]); } for(int i = 1; i <= A.size(); i++){ if(!hashset.count(i)) return i; } return A.size() + 1; } int firstMissingPositive(vector<int> A) { vector<int> hash(A.size() + 1, 0); for(int i = 0; i < A.size(); i++){ if(A[i] >= 1 && A[i] <= A.size()) hash[A[i]] = 1; } for(int i = 1; i <= A.size(); i++){ if(hash[i] == 0) return i; } return A.size() + 1; } };