Kth Missing Positive Number

Difficulty: Easy | Acceptance: 63.40% | Paid: No Topics: Array, Binary Search

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

Return the kth positive integer that is missing from this array.

• Examples
• Constraints
• Approach 1: Linear Scan
• Approach 2: Binary Search

Examples

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.

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 is sorted in a strictly increasing order.

Linear Scan

Intuition We can simulate the process of counting positive integers starting from 1. If the current number exists in the array, we skip it; otherwise, we count it as a missing number until we reach the kth missing one.

Steps

• Initialize a pointer i for the array and a counter missing for missing numbers.
• Iterate through positive integers starting from 1.
• If the current number matches arr[i], increment i to move to the next element in the array.
• If the current number does not match arr[i], increment missing.
• When missing equals k, return the current number.

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        missing_count = 0
        current = 1
        i = 0
        n = len(arr)
        while missing_count < k:
            if i < n and arr[i] == current:
                i += 1
            else:
                missing_count += 1
                if missing_count == k:
                    return current
            current += 1
        return -1

Complexity

• Time: O(n + k)
• Space: O(1)
• Notes: Simple to implement but can be slow if k is very large compared to n.

Binary Search

Intuition For any index i, the number of missing positive integers before arr[i] is given by arr[i] - i - 1. We can use binary search to find the smallest index left such that the number of missing integers before arr[left] is at least k. The answer is then left + k.

Steps

• Initialize left = 0 and right = arr.length - 1.
• While left <= right:
  • Calculate mid = left + (right - left) / 2.
  • Calculate missing = arr[mid] - mid - 1.
  • If missing < k, the kth missing number is to the right, so set left = mid + 1.
  • Otherwise, the kth missing number is to the left or at mid, so set right = mid - 1.
• After the loop, left is the insertion point. The kth missing number is left + k.

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = left + (right - left) // 2
            missing = arr[mid] - mid - 1
            if missing < k:
                left = mid + 1
            else:
                right = mid - 1
        return left + k

Complexity

• Time: O(log n)
• Space: O(1)
• Notes: Optimal solution for large input sizes.