Problem description:

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:

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 5th missing 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 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

Solution:

Relation between nums[idx] and idx could help to find missing number

We need a way to check on how many positive integers are missing before the given array element to use binary search. To do that, let’s compare the input array [2, 3, 4, 7, 11] with an array with no missing integers: [1, 2, 3, 4, 5]. The number of missing integers is a simple difference between the corresponding elements of these two arrays:

  • Before 2, there is 2 - 1 = 1 missing integer.
  • Before 3, there is 3 - 2 = 1 missing integer.
  • Before 4, there is 4 - 3 = 1 missing integer.
  • Before 7, there are 7 - 4 = 3 missing integers.
  • Before 11, there are 11 - 5 = 6 missing integers.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        l, r = 0, len(arr)-1
        while l <= r:
            mid = l + (r-l)//2
            # If number of positive integers
            # which are missing before arr[pivot]
            # is less than k -->
            # continue to search on the right.
            if arr[mid]-mid-1 < k:
                l = mid+1
            else:
                r = mid-1
            
        # At the end of the loop, left = right + 1,
        # and the kth missing is in-between arr[right] and arr[left].
        # The number of integers missing before arr[right] is
        # arr[right] - right - 1 -->
        # the number to return is
        # arr[right] + k - (arr[right] - right - 1) = k + left
        return l + k

time complexity: $O()$
space complexity: $O()$
reference:
related problem: