Problem Description

You are given an array arr containing positive integers that are sorted in strictly increasing order, and an integer k.

Your task is to find the kth positive integer that is missing from the array.

For example:

• If arr = [2, 3, 4, 7, 11] and k = 5, the missing positive integers are [1, 5, 6, 8, 9, ...]. The 5th missing positive integer is 9.
• If arr = [1, 2, 3, 4] and k = 2, the missing positive integers are [5, 6, 7, 8, ...]. The 2nd missing positive integer is 6.

The solution uses binary search to efficiently find the answer. The key insight is that for any index i in the array, the number of missing positive integers before arr[i] can be calculated as arr[i] - i - 1 (since if no numbers were missing, arr[i] would equal i + 1).

The algorithm:

1. First checks if the answer is before the first element (when arr[0] > k)
2. Uses binary search to find the position where exactly k missing numbers have occurred
3. Calculates the final answer based on the last element before the position found and adjusts for the remaining missing numbers needed

Intuition

The key observation is that if no positive integers were missing from the array, then arr[0] would be 1, arr[1] would be 2, and so on. In general, arr[i] would equal i + 1.

Since the array might have missing positive integers, we can calculate how many positive integers are missing before any element arr[i] using the formula: arr[i] - (i + 1) or simplified as arr[i] - i - 1.

For example, if arr[2] = 7 (at index 2), then ideally it should have been 3 if no numbers were missing. So the count of missing numbers before 7 is 7 - 2 - 1 = 4, which means the missing numbers are [1, 2, 4, 5] (assuming previous elements are 3 and 6).

This count of missing numbers increases as we move through the array. Since the array is sorted, we can use binary search to find the position where we've seen just enough missing numbers.

We're looking for the rightmost position where the count of missing numbers is less than k, or equivalently, the leftmost position where the count is at least k. Once we find this position, we know that:

• If we're at position left - 1, there are fewer than k missing numbers
• The kth missing number lies somewhere after arr[left - 1]

To find the exact value, we start from arr[left - 1] and add the remaining count needed. The remaining count is k minus the number of missing integers before arr[left - 1], which gives us: arr[left - 1] + (k - (arr[left - 1] - (left - 1) - 1)).

The special case at the beginning (if arr[0] > k) handles when the kth missing number appears before the first element of the array. For instance, if arr = [5, 6, 7] and k = 2, the missing numbers [1, 2, 3, 4] all come before arr[0], so the answer is simply k = 2.

Learn more about Binary Search patterns.

Solution Approach

The implementation uses binary search to efficiently find the position in the array where we have accumulated enough missing numbers.

Step 1: Handle the edge case

if arr[0] > k:
    return k

If the first element is greater than k, it means all k missing numbers occur before the array starts. For example, if arr = [5, 6, 7] and k = 3, the missing numbers are [1, 2, 3, 4, ...], so we simply return k.

Step 2: Binary search setup

left, right = 0, len(arr)

We initialize our search boundaries. Note that right is set to len(arr) (not len(arr) - 1) to handle cases where the answer might be after the last element.

Step 3: Binary search to find the critical position

while left < right:
    mid = (left + right) >> 1
    if arr[mid] - mid - 1 >= k:
        right = mid
    else:
        left = mid + 1

• Calculate mid using bit shift (>> 1 is equivalent to dividing by 2)
• Check how many missing numbers exist before arr[mid] using the formula arr[mid] - mid - 1
• If the count of missing numbers at mid is at least k, the answer is at or before mid, so we move right = mid
• Otherwise, we need to search further right, so left = mid + 1

After the binary search, left points to the first position where the count of missing numbers is at least k.

Step 4: Calculate the final answer

return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1)

At this point:

• arr[left - 1] is the largest element that has fewer than k missing numbers before it
• arr[left - 1] - (left - 1) - 1 gives us the count of missing numbers before arr[left - 1]
• We need to find the kth missing number, which is k - (count of missing before arr[left - 1]) positions after arr[left - 1]

The formula simplifies to adding the remaining missing count to arr[left - 1] to get our answer.

Time Complexity: O(log n) where n is the length of the array, due to binary search. Space Complexity: O(1) as we only use a constant amount of extra space.

Example Walkthrough

Let's walk through the solution with arr = [2, 3, 4, 7, 11] and k = 5.

Step 1: Check edge case

• Is arr[0] > k? Is 2 > 5? No, so we continue.

Step 2: Calculate missing numbers at each position Before we start binary search, let's understand what's happening at each index:

• Index 0: arr[0] = 2, missing count = 2 - 0 - 1 = 1 (missing: [1])
• Index 1: arr[1] = 3, missing count = 3 - 1 - 1 = 1 (missing: [1])
• Index 2: arr[2] = 4, missing count = 4 - 2 - 1 = 1 (missing: [1])
• Index 3: arr[3] = 7, missing count = 7 - 3 - 1 = 3 (missing: [1, 5, 6])
• Index 4: arr[4] = 11, missing count = 11 - 4 - 1 = 6 (missing: [1, 5, 6, 8, 9, 10])

Step 3: Binary search Initialize: left = 0, right = 5

Iteration 1:

• mid = (0 + 5) >> 1 = 2
• Missing at index 2: arr[2] - 2 - 1 = 4 - 2 - 1 = 1
• Is 1 >= 5? No, so left = mid + 1 = 3

Iteration 2:

• mid = (3 + 5) >> 1 = 4
• Missing at index 4: arr[4] - 4 - 1 = 11 - 4 - 1 = 6
• Is 6 >= 5? Yes, so right = mid = 4

Iteration 3:

• mid = (3 + 4) >> 1 = 3
• Missing at index 3: arr[3] - 3 - 1 = 7 - 3 - 1 = 3
• Is 3 >= 5? No, so left = mid + 1 = 4

Loop ends as left = right = 4.

Step 4: Calculate the answer

• left - 1 = 3, so we look at arr[3] = 7
• Missing numbers before arr[3]: 7 - 3 - 1 = 3
• We need the 5th missing number, so we need 5 - 3 = 2 more missing numbers after arr[3]
• Answer: arr[3] + (k - missing_before) = 7 + (5 - 3) = 7 + 2 = 9

Let's verify: The missing positive integers are [1, 5, 6, 8, 9, ...]. The 5th one is indeed 9. ✓

Solution Implementation

Time and Space Complexity

Time Complexity: O(log n) where n is the length of the input array arr.

The algorithm uses binary search on the array. The binary search performs at most log n iterations since it halves the search space in each iteration. Each iteration performs constant time operations:

• Calculating mid = (left + right) >> 1 is O(1)
• Accessing arr[mid] and performing arithmetic operations arr[mid] - mid - 1 is O(1)
• Comparing and updating left or right is O(1)

The initial check if arr[0] > k and the final calculation are both O(1) operations.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variables left, right, and mid for the binary search
• No additional data structures are created
• No recursive calls that would use the call stack

The space used does not depend on the size of the input array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Out of Bounds Error

The most common pitfall occurs when calculating the final answer. After the binary search, if left becomes 0 (when all k missing numbers should come before the first element), accessing arr[left - 1] will cause an index out of bounds error.

Problematic scenario:

arr = [5, 6, 7], k = 2
# After binary search, left = 0
# arr[left - 1] = arr[-1] → IndexError!

Solution: Add a check after the binary search to handle this edge case:

if left == 0:
    return k

2. Integer Overflow in Binary Search

When calculating mid = (left + right) // 2, if the array is extremely large, left + right could potentially overflow in some languages (though Python handles big integers well).

Solution: Use the alternative formula to avoid overflow:

mid = left + (right - left) // 2

3. Incorrect Binary Search Boundaries

Setting right = len(arr) - 1 instead of right = len(arr) will cause incorrect results when the answer lies after the last element of the array.

Problematic scenario:

arr = [1, 2, 3], k = 5
# With right = len(arr) - 1, the search space doesn't include the possibility
# that all k missing numbers are after the array

Solution: Always initialize right = len(arr) to ensure the search space includes positions beyond the array.

4. Off-by-One Error in Missing Count Formula

Forgetting the -1 in the formula arr[i] - i - 1 is a frequent mistake. The formula represents: (value at index i) - (expected value if no gaps) = missing count.

Wrong formula: arr[i] - i Correct formula: arr[i] - i - 1

Example to remember: If arr = [2] at index 0, missing count should be 1 (the number 1 is missing).

• Wrong: 2 - 0 = 2 (incorrect)
• Correct: 2 - 0 - 1 = 1 (correct)

5. Not Handling Empty Array Edge Case

Though not typically expected in this problem, an empty array would cause immediate failure.

Solution: Add a check at the beginning:

if not arr:
    return k

Complete Corrected Solution:

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        if not arr:
            return k
          
        if arr[0] > k:
            return k
      
        left, right = 0, len(arr)
      
        while left < right:
            mid = left + (right - left) // 2
            missing_count = arr[mid] - mid - 1
          
            if missing_count >= k:
                right = mid
            else:
                left = mid + 1
      
        # Handle the case when left == 0
        if left == 0:
            return k
          
        prev_index = left - 1
        missing_before_prev = arr[prev_index] - prev_index - 1
        return arr[prev_index] + k - missing_before_prev