Kth Missing Positive Number
EasyPrompt
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]for1 <= i < j <= arr.length
Follow up:
Could you solve this problem in less than O(n) complexity?
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves a straightforward simulation. We first store all numbers from the input array into a HashSet for quick O(1) average time lookups. Then, we iterate through positive integers starting from 1, and for each integer, we check if it's in our set. If it's not, we've found a missing number and we decrement k. The process stops when k reaches zero, and the current integer is our answer.
Algorithm
- Create a
HashSetand populate it with all the elements from the input arrayarr. - Initialize a counter for the current positive integer,
num = 1, and a counter for missing numbers found,missingCount = 0. - Start a loop that continues as long as
kis greater than 0. - Inside the loop, check if the current
numis present in theHashSet. - If
numis not in the set, it's a missing number. Decrementk. - If
kbecomes 0, then the currentnumis the k-th missing number, so we return it. - Increment
numin every iteration to check the next positive integer.
Walkthrough
The brute-force method systematically checks every positive integer to see if it is missing from the given array. To do this efficiently, we first convert the arr into a HashSet. This data structure provides average constant-time complexity for checking the existence of an element.
We then iterate upwards from the number 1. In each step, we see if the current number is in the set. If it is, we continue to the next number. If it's not, we've found a missing number. We decrement our counter k. When k hits zero, we have found our target, the k-th missing positive integer.
import java.util.HashSet;import java.util.Set; class Solution { public int findKthPositive(int[] arr, int k) { Set<Integer> numSet = new HashSet<>(); for (int num : arr) { numSet.add(num); } int num = 1; while (k > 0) { if (!numSet.contains(num)) { k--; } if (k == 0) { return num; } num++; } return -1; // Should not be reached given the constraints }}Complexity
Time
O(N + M), where N is the length of `arr` and M is the value of the k-th missing number. Building the set takes O(N). The loop runs M times. In the worst case, M can be `arr.length + k`, so the complexity is O(N + k).
Space
O(N), where N is the number of elements in the array `arr`. This space is used to store the elements in a `HashSet`.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem.
Cons
Inefficient in terms of both time and space compared to other solutions.
The time complexity depends on the value of the result, which can be large.
A more efficient approach is to perform a single linear scan through the array. Since the array is sorted, we can keep track of k and adjust it as we encounter numbers. The core idea is that if we see a number num from the array that is less than or equal to our current target k, it 'uses up' a spot, so we need to find the (k+1)-th missing number instead. This simple adjustment allows us to find the answer in one pass.
Algorithm
- Iterate through each number
numin the sorted input arrayarr. - For each
num, check if it is less than or equal to the current value ofk. - If
num <= k, it means this number from the array occupies a spot that would have otherwise been one of the firstkmissing integers. To compensate for this, we must look for a number that is one position further. So, we incrementk. - If
num > k, it means the k-th missing number must have come beforenum, and we have already passed it. We can stop iterating. - After the loop finishes (or breaks), the final value of
kis the k-th missing positive integer.
Walkthrough
This approach leverages the sorted nature of the array to avoid using extra space. We can think of the problem as finding the value k in a sequence where some numbers (those in arr) are skipped.
We initialize our answer to be k. We then iterate through the array arr. For each element arr[i], if arr[i] is less than or equal to our current answer k, it means the number arr[i] is present and is taking up a spot at or before our target. This implies that our target missing number must be shifted one position to the right. Therefore, we increment k.
Once we encounter an arr[i] that is greater than k, we know that the k-th missing number has already been determined, as no subsequent numbers in the array can affect it. The final value of k after the iteration is the result.
class Solution { public int findKthPositive(int[] arr, int k) { for (int num : arr) { if (num <= k) { k++; } else { break; } } return k; }}Complexity
Time
O(N), where N is the length of the array `arr`. In the worst case, we iterate through the entire array once.
Space
O(1), as we only use a few variables to keep track of our state, regardless of the input size.
Trade-offs
Pros
Very efficient in terms of space, using only O(1) extra space.
Simple and elegant logic.
Time complexity is linear, which is a significant improvement over the brute-force method.
Cons
Not as efficient as the binary search approach for very large arrays, as it has a linear time complexity.
The most optimal solution uses binary search to achieve logarithmic time complexity, which directly addresses the follow-up question. The key observation is that the number of missing integers up to any given index i (arr[i] - (i + 1)) is a monotonically increasing function. This allows us to efficiently search for the point in the array where the count of missing numbers surpasses k.
Algorithm
- The number of missing positive integers before
arr[i]isarr[i] - (i + 1). - This count of missing numbers is a non-decreasing function of the index
i, which allows us to use binary search. - We binary search on the indices of
arrfromleft = 0toright = arr.length - 1. - In each step, we calculate the
midindex and find the number of missing integers up to that point:missing = arr[mid] - (mid + 1). - If
missing < k, it means the k-th missing number is in the right part of the array. We updateleft = mid + 1. - If
missing >= k, the k-th missing number is in the left part (or atmid), so we updateright = mid - 1. - The loop terminates when
left > right. The value ofleftat the end of the loop represents the number of elements fromarrthat are smaller than our answer. - The k-th missing number is the k-th positive integer after skipping these
leftnumbers. Thus, the answer isk + left.
Walkthrough
This approach is based on a key insight: for any element arr[i], we know that there should be i + 1 positive integers up to that position if the array were dense (i.e., [1, 2, 3, ...]). Therefore, the number of positive integers missing before arr[i] is exactly arr[i] - (i + 1).
Since arr is strictly increasing, the function f(i) = arr[i] - (i + 1) is non-decreasing. This property is perfect for binary search. Our goal is to find the index i such that the k-th missing number lies between arr[i-1] and arr[i].
We perform a binary search on the array's indices. For each mid index, we check if arr[mid] - (mid + 1) is less than k.
- If it is, we know the k-th missing number must be further to the right, so we discard the left half by setting
left = mid + 1. - Otherwise, the k-th missing number is to the left of or at
mid's position, so we setright = mid - 1.
When the search concludes, left will point to the index where the k-th missing number would be inserted. The final answer is k + left, because there are left numbers from arr that are smaller than the result, and we are looking for the k-th missing number.
class Solution { public int findKthPositive(int[] arr, int k) { int left = 0; int right = arr.length - 1; while (left <= right) { int mid = left + (right - left) / 2; // Number of missing integers before arr[mid] int missingCount = arr[mid] - (mid + 1); if (missingCount < k) { left = mid + 1; } else { right = mid - 1; } } // At the end of the loop, `left` is the number of elements // in `arr` that are smaller than the k-th missing number. // The k-th missing number is k + left. return left + k; }}Complexity
Time
O(log N), where N is the length of the array `arr`. This is due to the binary search algorithm, which halves the search space in each iteration.
Space
O(1), as the binary search is performed in-place and uses only a few variables for pointers.
Trade-offs
Pros
Extremely efficient with O(log N) time complexity.
Optimal solution for the problem.
Uses O(1) space.
Cons
The logic can be less intuitive to grasp compared to a straightforward linear scan.
Solutions
Solution
class Solution {public int findKthPositive(int[] arr, int k) { if (arr[0] > k) { return k; } int left = 0, right = arr.length; while (left < right) { int mid = (left + right) >> 1; if (arr[mid] - mid - 1 >= k) { right = mid; } else { left = mid + 1; } } return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1); }}class Solution {public: int findKthPositive(vector<int> &arr, int k) { if (arr[0] > k) return k; int left = 0, right = arr.size(); while (left < right) { int mid = (left + right) >> 1; if (arr[mid] - mid - 1 >= k) right = mid; else left = mid + 1; } return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1); }};class Solution: def findKthPositive(self, arr: List[int], k: int) -> int: if arr[0] > k: return k left, right = 0, len(arr) while left < right: mid = (left + right) >> 1 if arr[mid] - mid - 1 >= k: right = mid else: left = mid + 1 return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.