1539. Kth Missing Positive Number

Posted on Edited on In

1539. Kth Missing Positive Number

Description

Given an array arr of positive integers sorted in a strictly increasing order , and an integer k.

Return the k^th positive integer that is missing from this array.

Example 1:

1
2
3
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 5^thmissing positive integer is 9.

Example 2:

1
2
3
Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2^nd 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

Follow up:

Could you solve this problem in less than O(n) complexity?

Hints/Notes

Solution

Language: C++

O(log(n)) solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        // for each index of arr, there are arr[idx] - idx - 1 numbers skipped
        // before this number
        // for idx < left, skipped <= k is always true
        int left = -1, right = arr.size();
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            int skipped = arr[mid] - mid - 1;
            if (skipped >= k) {
                right = mid;
            } else {
                left = mid;
            }
        }
        //
        return left >= 0 ? k - (arr[left] - left - 1) + arr[left] : k;
    }
};

O(n) solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        for (int num : arr) {
            if (num <= k) {
                k++;
            } else {
                break;
            }
        }
        return k;
    }
};