Algorithm to Find the Kth Missing Positive Number in Array

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k. Find the kth positive integer that is missing from this array.

Example 1:
Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,…]. The 5th missing positive integer is 9.

Example 2:
Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,…]. The 2nd missing positive integer is 6.

Constraints:
1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

Hints:
Keep track of how many positive numbers are missing as you scan the array.

Using a Hash Set to Compute the Kth Missing Positive Number in the Array

We can convert the input array into a hash set, then intuitively, we can skip and count the first k numbers before we find the missing numebr.

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

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        unordered_set<int> data(begin(arr), end(arr));
        int j = 1;
        for (int i = 0; i < k; ++ i) {
            while (data.count(j)) j ++;
            j ++;
        }
        return j - 1;
    }
};

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        unordered_set<int> data(begin(arr), end(arr));
        int j = 1;
        for (int i = 0; i < k; ++ i) {
            while (data.count(j)) j ++;
            j ++;
        }
        return j - 1;
    }
};

The runtime complexity is O(K) if K is not bounded to [1..1000]. The space requirement is O(N) because of using the hash set.

Compute the Kth Missing Positive Number in the Array using Binary Search Algorithm

If the final result is k, therefore there are m numbers not missing in the range of 1 to k. We can binary search the m in the range of 0 to the size. The number of missing numbers between A[0] to A[m-1] is A[m-1] – m.

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

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int l = 0, r = A.size(), m;
        while (l < r) {
            m = (l + r + 1) / 2;
            if (m == 0 || A[m - 1] - m < k) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        return l + k;
    }
};

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int l = 0, r = A.size(), m;
        while (l < r) {
            m = (l + r + 1) / 2;
            if (m == 0 || A[m - 1] - m < k) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        return l + k;
    }
};

The time complexity is O(LogN) and the space requirement is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —