Coding Exercise – First Missing Positive – C++ – Online Judge

Question:  Given an unsorted list of integers, find out the first missing positive.

Problem Description: http://oj.leetcode.com/problems/first-missing-positive/

Examples: [1, 2, 0]  should return 3;   [3, 4, -1, 1] should return 2. Can you do it with O(n) time complexity and O(1) constant space?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        bool *arr = new bool[n + 1]; // O(n) space
        for (int i = 0; i < n; i ++) {             
                if ((A[i] >= 0) && (A[i] <= n)) {
                        arr[A[i]] = true; // mark A[i] present
                }
        } // up to this bit, we've actually sorted the numbers
        for (int i = 1; i <= n; i ++) {
            if (!arr[i]) return i; // not marked, so missing
        }
        return n + 1;// all marked, so the first missing is n + 1
    }
};

class Solution {
public:
    int firstMissingPositive(int A[], int n) {
        bool *arr = new bool[n + 1]; // O(n) space
        for (int i = 0; i < n; i ++) {             
                if ((A[i] >= 0) && (A[i] <= n)) {
                        arr[A[i]] = true; // mark A[i] present
                }
        } // up to this bit, we've actually sorted the numbers
        for (int i = 1; i <= n; i ++) {
            if (!arr[i]) return i; // not marked, so missing
        }
        return n + 1;// all marked, so the first missing is n + 1
    }
};

There are some hints to solve this problem nicely. n integers are given (negatives, zero and positives). So if the worst case, all numbers are positives (1, 2, 3, … n), the first missing positive would be n + 1. In all other cases, the first missing positive would be from 1 to n inclusive.

It is unsorted array. We create another array (O(n)), to hold the booleans that if numbers appear in inputs. Initialize the array to all false (which can be omitted by default), iterative over the inputs, and mark (if the value in range) the corresponding boolean to true meaning that this number is not missing. At the end we would just have to check from index one to the end that if the corresponding boolean is false. If it is false, it means this number has not appeared in the inputs, so it is the first missing positive!

The first half of the algorithm acts as like a index sorting algorithm where you place element to the position according to its index.

The overall algorithm complexity if O(n).

Using Set

We can use STL:set to mark the appearance for the positive numbers:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> cache;
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] > 0) {
                cache.insert(nums[i]);
            }
        }
        for (int i = 1; ; i ++) {
            if (!cache.count(i)) { // first missing positive
                return i; 
            }
        }
    }
};

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        unordered_set<int> cache;
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] > 0) {
                cache.insert(nums[i]);
            }
        }
        for (int i = 1; ; i ++) {
            if (!cache.count(i)) { // first missing positive
                return i; 
            }
        }
    }
};

O(n) time and constant space

We can re-arrange the elements so that the integer x should be in the array nums[x – 1]. We repeatedly swap the elements until they are in correct places or out of the range (non-positive or larger than the size of array). The answer would be the first element that is not in its position.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++ i) {
            int x = nums[i];
            while (x > 0 && x <= n && nums[x - 1] != x) { // element is not in its position
                swap(nums[i], nums[x - 1]);
                x = nums[i];
            }
        }
        for (int i = 0; i < n; ++ i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++ i) {
            int x = nums[i];
            while (x > 0 && x <= n && nums[x - 1] != x) { // element is not in its position
                swap(nums[i], nums[x - 1]);
                x = nums[i];
            }
        }
        for (int i = 0; i < n; ++ i) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        return n + 1;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —