Solution Approach

The implementation uses binary search with the standard template to find the first position where the count of missing numbers reaches k.

Feasible Function Definition

For any index i, the number of missing positive integers before arr[i] is arr[i] - i - 1. This is because if no numbers were missing, arr[i] would equal i + 1.

We define feasible(mid) = arr[mid] - mid - 1 >= k, which returns true when at least k numbers are missing before position mid. This creates the pattern:

[false, false, ..., false, true, true, ..., true]

We want to find the first index where this becomes true.

Binary Search Template

left, right = 0, len(arr) - 1
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if arr[mid] - mid - 1 >= k:  # feasible(mid)
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

Calculating the Final Answer

After the binary search:

• If first_true_index == -1: No position has k missing numbers, so the answer is after the array
• If first_true_index == 0 and arr[0] > k: All k missing numbers are before the array starts, return k
• Otherwise: The answer lies between arr[first_true_index - 1] and arr[first_true_index]

When first_true_index > 0, we use arr[first_true_index - 1] as the anchor point. The count of missing numbers before this position is arr[first_true_index - 1] - (first_true_index - 1) - 1. The k-th missing number is arr[first_true_index - 1] + (k - missing_count).

Time Complexity: O(log n) where n is the length of the array. 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 with binary search.

Step 2: Understand the feasible function Before binary search, let's see the missing count at each index:

• Index 0: arr[0] = 2, missing = 2 - 0 - 1 = 1, feasible(0) = 1 >= 5? false
• Index 1: arr[1] = 3, missing = 3 - 1 - 1 = 1, feasible(1) = 1 >= 5? false
• Index 2: arr[2] = 4, missing = 4 - 2 - 1 = 1, feasible(2) = 1 >= 5? false
• Index 3: arr[3] = 7, missing = 7 - 3 - 1 = 3, feasible(3) = 3 >= 5? false
• Index 4: arr[4] = 11, missing = 11 - 4 - 1 = 6, feasible(4) = 6 >= 5? true

Pattern: [false, false, false, false, true] → first_true_index should be 4.

Step 3: Binary search using template Initialize: left = 0, right = 4, first_true_index = -1

Iteration 1: left=0, right=4

• mid = (0 + 4) // 2 = 2
• Missing at index 2: 4 - 2 - 1 = 1
• Is 1 >= 5? No (not feasible)
• left = mid + 1 = 3

Iteration 2: left=3, right=4

• mid = (3 + 4) // 2 = 3
• Missing at index 3: 7 - 3 - 1 = 3
• Is 3 >= 5? No (not feasible)
• left = mid + 1 = 4

Iteration 3: left=4, right=4

• mid = (4 + 4) // 2 = 4
• Missing at index 4: 11 - 4 - 1 = 6
• Is 6 >= 5? Yes (feasible!)
• first_true_index = 4, right = mid - 1 = 3

Loop ends as left > right (4 > 3).

Step 4: Calculate the answer

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

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

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. Using Wrong Binary Search Template Variant

A common mistake is using while left < right with right = mid instead of the standard template with first_true_index tracking.

Wrong variant:

while left < right:
    mid = (left + right) // 2
    if arr[mid] - mid - 1 >= k:
        right = mid
    else:
        left = mid + 1
return arr[left - 1] + ...  # Prone to index errors!

Correct template:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if arr[mid] - mid - 1 >= k:
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1
# Handle first_true_index == -1 case explicitly

2. Index Out of Bounds When first_true_index is -1

After binary search, if no position satisfies the feasible condition, first_true_index remains -1. Accessing arr[first_true_index - 1] without checking causes errors.

Solution: Always check if first_true_index == -1 before using it:

if first_true_index == -1:
    # Handle case where k-th missing is after the array
    last_idx = len(arr) - 1
    return arr[last_idx] + (k - (arr[last_idx] - last_idx - 1))

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

Forgetting the -1 in the formula arr[i] - i - 1 is a frequent mistake.

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

Example: 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)

4. Not Handling Edge Case When first_true_index is 0

When first_true_index == 0, the k-th missing number is before arr[0]. Trying to access arr[first_true_index - 1] causes an index error.

Solution:

if first_true_index == 0:
    return k  # All k missing numbers are before arr[0]

5. Integer Overflow in Mid Calculation

In some languages, (left + right) / 2 can overflow for large values.

Solution:

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

Template-Compliant Solution:

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        if arr[0] > k:
            return k

        left, right = 0, len(arr) - 1
        first_true_index = -1

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

        if first_true_index == -1:
            last_idx = len(arr) - 1
            return arr[last_idx] + (k - (arr[last_idx] - last_idx - 1))
        elif first_true_index == 0:
            return k
        else:
            prev_idx = first_true_index - 1
            return arr[prev_idx] + (k - (arr[prev_idx] - prev_idx - 1))