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.
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); }}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.