Kth Missing Positive Number

LeetCode 1539: Kth Missing Positive Number Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses binary search to find the first index where the number of missing integers exceeds k, deriving the result from the final search position in $O(\log N)$ time.

The Kth Missing Positive Number problem asks us to identify the $k$-th positive integer that does not appear in a given sorted array arr. The array consists of positive integers in strictly increasing order. While the problem can be solved by iterating through the numbers linearly, the sorted nature of the input suggests a more efficient logarithmic time complexity solution, which is a popular interview question requirement.

Brute Force Approach for Kth Missing Positive Number

A naive approach is to iterate through the array and count how many numbers are missing as we progress. Since the array is sorted, we can compare the current value arr[i] with the expected value if no numbers were missing (which would be i + 1).

Alternatively, we can iterate through all positive integers starting from 1. We check if the current integer exists in the array. If it does not, we decrement k. When k reaches 0, the current integer is our answer.

Naive Algorithm:

1. Initialize a pointer for the array and a counter for the current positive integer.
2. Loop while k > 0.
3. Check if the current integer matches the current array element.
4. If yes, move the array pointer.
5. If no, decrement k (we found a missing number).
6. Increment the current integer.
7. Return the integer that caused k to reach 0.

Time Complexity: $O(N + K)$. In the worst case, if $k$ is very large, we might iterate far beyond the array bounds. Why it fails: While this passes small constraints, the follow-up explicitly asks for a solution with less than $O(N)$ complexity. For very large $N$ or $K$, linear scanning is suboptimal compared to binary search.

Algorithm Strategy: Binary Search Patterns

We utilize the standard Binary Search template to locate the partition point in the array.

1. Initialize Pointers: Set left = 0 and right = arr.length - 1.
2. Binary Search Loop: While left <= right:
   • Calculate mid.
   • Compute missing = arr[mid] - (mid + 1).
   • Decision Logic:
     • If missing < k: It means the $k$-th missing number is to the right of mid. We have not skipped enough numbers yet. Move left to mid + 1.
     • If missing >= k: It means the $k$-th missing number is to the left of mid (or could be before arr[mid]). Move right to mid - 1.
3. Derive Result: When the loop terminates, left points to the index where the missing count would theoretically exceed or equal k. The formula for the answer is derived mathematically as left + k.

Execution Flow

Let's trace arr = [2, 3, 4, 7, 11] and k = 5.

1. Start: left = 0, right = 4.
2. Iteration 1:
   • mid = 2. arr[2] = 4.
   • missing = 4 - (2 + 1) = 1.
   • Since 1 < 5, we need more missing numbers.
   • left = mid + 1 = 3.
3. Iteration 2:
   • mid = 3. arr[3] = 7.
   • missing = 7 - (3 + 1) = 3.
   • Since 3 < 5, we need more missing numbers.
   • left = mid + 1 = 4.
4. Iteration 3:
   • mid = 4. arr[4] = 11.
   • missing = 11 - (4 + 1) = 6.
   • Since 6 >= 5, the target is to the left.
   • right = mid - 1 = 3.
5. Termination:
   • left (4) is now greater than right (3). Loop ends.
6. Calculation:
   • Result = left + k = 4 + 5 = 9.
   • Verification: Missing numbers are 1, 5, 6, 8, 9. The 5th is indeed 9.

Proof of Correctness

Why is the answer left + k?

At the end of the binary search, right is the largest index such that arr[right] - (right + 1) < k. The variable left is equal to right + 1. The number of missing integers strictly before arr[right] is missing_count = arr[right] - (right + 1). Since missing_count < k, the $k$-th missing number is located after arr[right]. Specifically, we need to find the $(k - \text{missing\_count})$-th missing number starting after arr[right].

Since there are no elements between arr[right] and the theoretical missing number we are looking for (because arr is sorted and we are looking in the gap), the numbers immediately following arr[right] are missing. The answer is: $\text{Answer} = \text{arr}[right] + (k - \text{missing\_count})$ Substitute missing_count: $\text{Answer} = \text{arr}[right] + k - (\text{arr}[right] - (right + 1))$ $\text{Answer} = \text{arr}[right] + k - \text{arr}[right] + right + 1$ $\text{Answer} = k + right + 1$ Since left = right + 1, the formula simplifies to: $\text{Answer} = k + left$

This derivation holds even for edge cases (e.g., when the missing number is before the first element or after the last).

Pattern Reuse Notes

The Binary Search - On Sorted Array/List pattern is fundamental for solving problems where we need to locate an element or a condition in a monotonic sequence.

• LeetCode 35: Search Insert Position: Finds the index where a value should be inserted to maintain order, similar to finding the "gap" in this problem.
• LeetCode 69: Sqrt(x): Searches for a value $val$ such that $val^2 \le x$, relying on the monotonic nature of squares.
• LeetCode 74: Search a 2D Matrix: Treats a 2D matrix as a flattened sorted list to apply binary search.
• LeetCode 278: First Bad Version: Finds the boundary between "good" and "bad" versions, analogous to finding the boundary where missing counts exceed k.

Reference Implementation

C++ Solution for LeetCode 1539

1class Solution {
2public:
3    int findKthPositive(vector<int>& arr, int k) {
4        int left = 0;
5        int right = arr.size() - 1;
6
7        while (left <= right) {
8            int mid = left + (right - left) / 2;
9            // Calculate how many numbers are missing up to index mid
10            int missing = arr[mid] - (mid + 1);
11
12            if (missing < k) {
13                // If missing count is less than k, the answer is to the right
14                left = mid + 1;
15            } else {
16                // If missing count is >= k, the answer is to the left
17                right = mid - 1;
18            }
19        }
20
21        // The formula derived in the proof: k + left
22        return left + k;
23    }
24};

Java Solution for LeetCode 1539

1class Solution {
2    public int findKthPositive(int[] arr, int k) {
3        int left = 0;
4        int right = arr.length - 1;
5
6        while (left <= right) {
7            int mid = left + (right - left) / 2;
8            // Calculate how many numbers are missing up to index mid
9            int missing = arr[mid] - (mid + 1);
10
11            if (missing < k) {
12                // We need more missing numbers, so look right
13                left = mid + 1;
14            } else {
15                // We have enough missing numbers, so look left
16                right = mid - 1;
17            }
18        }
19
20        // Based on the derivation: answer = k + left
21        return left + k;
22    }
23}

Python Solution for LeetCode 1539

1class Solution:
2    def findKthPositive(self, arr: List[int], k: int) -> int:
3        left, right = 0, len(arr) - 1
4        
5        while left <= right:
6            mid = left + (right - left) // 2
7            # Calculate missing count at index mid
8            missing = arr[mid] - (mid + 1)
9            
10            if missing < k:
11                # Not enough missing numbers yet, move right
12                left = mid + 1
13            else:
14                # Enough or too many missing numbers, move left
15                right = mid - 1
16                
17        # The result is derived as k + left
18        return left + k