First Missing Integer

First Missing Integer - InterviewBitInterviewBit

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

Brute Force

Code

int Solution::firstMissingPositive(vector<int> &A) {
    for(int i = 1; i <= A.size() + 1; i++) {
        bool found = false;
        for(int j = 0; j < A.size(); j++)
            if(A[j] == i) {
                found = true;
                break;
            }
        if(!found)
            return i;
    }
    return -1;
}

Time Complexity: $O(n^2)$​

Space Complexity: $O(1)$

Using Sorting

Code

int Solution::firstMissingPositive(vector<int> &A) {
    sort(A.begin(), A.end());
    int expected = 1;
    for(int x: A)
        if(x > expected)
            return expected;
        else if(x == expected)
            expected++;

    return expected;
}

Time Complexity: $O(n\log n)$​

Space Complexity: $O(1)$

Using lookup table

Code

int Solution::firstMissingPositive(vector<int> &A) {
    vector<bool> seen(A.size() + 1, false);

    for(int x: A)
        seen[x] = true;

    for(int i = 1; i < seen.size(); i++)
        if(!seen[i])
            return i;

    return -1;    
}

Time Complexity: $O(n)$

Space Complexity: $O(n)$

Optimal Solution Cyclic Sort

Code

int Solution::firstMissingPositive(vector<int> &A) {
    int n = A.size();
    for(int i = 0; i < n; i++) 
        if(A[i] > 0 && A[i] <= n) {
            int pos = A[i] - 1;
            if(A[pos] != A[i]) {
                swap(A[pos], A[i]);
                i--;
            }
        }
    
    for(int i = 0; i < n; i++)
        if(A[i] != i + 1) return (i + 1);

    return n + 1;
}

Time Complexity: $O(n)$​

Space Complexity: $O(1)$