1539. Kth Missing Positive Number

1539. Kth Missing Positive Number (Easy)

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

Related Topics:
Array, Hash Table

Solution 1. Brute Force

// OJ: https://leetcode.com/problems/kth-missing-positive-number/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int findKthPositive(vector<int>& A, int k) {
        for (int i = 1, j = 0; i <= 2000; ++i) {
            if (j < A.size() && A[j] == i) ++j;
            else if (--k == 0) return i;
        }
        return -1;
    }
};

Or

// OJ: https://leetcode.com/problems/kth-missing-positive-number/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int findKthPositive(vector<int>& A, int k) {
        for (int i = 1, j = 0; i <= 1000; ++i) {
            if (j < A.size() && A[j] == i) ++j;
            else if (--k == 0) return i;
        }
        return 1000 + k;
    }
};

Solution 2. Binary Search

For the first i + 1 numbers in A, the count of missing numbers in these i + 1 numbers is miss(i) = A[i] - i - 1.

Example:

A=[1,4,5,8]
i=2
miss(2) = A[2] - 2 - 1 = 2 // There are two missing numbers in [1,4,5].

We can binary search the greatest index i which satisfies miss(i) < k. Assume it's x, then x + k + 1 is the answer. It's because adding x + 1(the count of existing numbers) to k (the index of the target missing number) will get the answer (the value of the target missing number).

Example,

A=[1,4,5,8]
k=4
For i = 2, miss(2) = 2 < k
For i = 3, miss(3) = 4 >= k
So x = 2
The answer is x + k + 1 = 7 

The range of the index to search is [0, N - 1]. When miss(M) < k, L = M + 1; otherwise, R = M - 1.

Then in the end, R will be the x, i.e. the greatest index that miss(R) < k. So the answer is R + k + 1, or L + k.

// OJ: https://leetcode.com/problems/kth-missing-positive-number/
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
public:
    int findKthPositive(vector<int>& A, int k) {
        int L = 0, R = A.size() - 1;
        while (L <= R) {
            int M = (L + R) / 2;
            if (A[M] - M - 1 < k) L = M + 1;
            else R = M - 1;
        }
        return L + k;
    }
};