Kth Missing Positive Number - Video Solutions

Problem Overview: You are given a strictly increasing sorted array of positive integers. Some numbers are missing from the sequence starting at 1. The task is to return the k-th missing positive number that does not appear in the array.

Approach 1: Iterative Approach (O(n) time, O(1) space)

This method walks through the array while tracking how many numbers are missing before each element. For an index i, the number of missing integers before arr[i] equals arr[i] - (i + 1). That expression works because a perfect sequence without gaps would contain i + 1 numbers up to that index. As you iterate, compare the missing count with k. Once the missing count becomes greater than or equal to k, the answer lies before the current element and can be computed directly using arithmetic. If the loop finishes without reaching k, the remaining missing numbers occur after the last element, so you extend the sequence beyond arr[n-1]. This approach is simple and reliable when scanning the array once is acceptable.

The technique relies only on index arithmetic and sequential traversal, making it a clean application of basic array processing. Interviewers often expect candidates to derive the missing-count formula during discussion because it shows you understand how indices relate to ideal sequences.

Approach 2: Binary Search Optimization (O(log n) time, O(1) space)

The sorted property of the array enables a faster solution using binary search. Instead of scanning every element, search for the first index where the number of missing values becomes at least k. At each midpoint mid, compute the missing count using the same formula: missing = arr[mid] - (mid + 1). If this value is less than k, move the search window to the right. Otherwise, move left to find the earliest position where the missing count reaches k.

After the search finishes, the answer can be derived using the final left boundary. The key observation: the k-th missing number must appear between two array elements or after the array ends. Binary search efficiently finds that boundary in logarithmic time without explicitly enumerating missing values.

This optimization becomes valuable when the array is large. The algorithm performs only logarithmic comparisons while still using constant memory.

Recommended for interviews: Start by explaining the iterative logic because it clearly demonstrates how missing numbers relate to array indices. Once that idea is established, transition to the binary search solution. Interviewers usually expect the optimized O(log n) approach for a sorted array, since recognizing the monotonic missing-count pattern shows strong algorithmic reasoning.