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.
Example 1:
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.
Example 2:
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 <= 10001 <= arr[i] <= 10001 <= k <= 1000arr[i] < arr[j] for 1 <= i < j <= arr.length
Follow up:
Could you solve this problem in less than O(n) complexity?
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.
This approach involves iterating through the array and maintaining a counter for missing positive integers. We start with the first positive number, which is 1, and determine if it is missing by comparing it to the current element in the array. If the number is missing, we decrement our k value. When k reaches zero, we have found our k-th missing number.
This C solution uses a simple iteration where it keeps track of what the next missing number should be while iterating over the array. It compares the current number to the next expected missing number. If the expected number is equal to the array number, it means the number is not missing, so it moves to the next array element. Otherwise, it increases the missing count and checks if it matches k.
Time Complexity: O(n + k), where n is the length of the array. Space Complexity: O(1), as we are using constant extra space.
By using binary search, a more efficient solution can be developed that reduces unnecessary checks. The key observation is that the number of missing integers before arr[i] can be calculated as arr[i] - (i + 1), which helps in deducing the position of the k-th missing number without iterating through every integer.
This implementation uses binary search to efficiently find the k-th missing positive number. The search focuses on a "missing" variable that tells how many numbers are missing up to the mid-point in the array.
Time Complexity: O(log n), Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n + k), where n is the length of the array. Space Complexity: O(1), as we are using constant extra space. |
| Binary Search Optimization | Time Complexity: O(log n), Space Complexity: O(1). |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Approach | O(n) | O(1) | Simple implementation when scanning the array once is acceptable |
| Binary Search Optimization | O(log n) | O(1) | Best choice for large sorted arrays where logarithmic search improves performance |
BS-16. Kth Missing Positive Number | Maths + Binary Search • take U forward • 347,793 views views
Watch 9 more video solutions →Practice Kth Missing Positive Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor