Kth Missing Positive Number solution and explanation
Google
IBM
9 more videos on this problem
BS-16. Kth Missing Positive Number | Maths + Binary Searchtake U forward · 22:52 · 388K views
Kth Missing Positive Number | 2 Approaches | codestorywithMIKcodestorywithMIK · 23:15 · 24K views
Kth Missing Positive Number | Live Coding with Explanation | Leetcode #1539Algorithms Made Easy · 7:16 · 23K views
Kth Missing Positive Number (LeetCode 1539) | Full Solution with intuition, animations and visualsNikhil Lohia · 18:36 · 15K views
K-TH MISSING POSITIVE NUMBER | LEETCODE 1539 | PYTHON SOLUTIONCracking FAANG · 11:00 · 10K views
Kth Missing Positive Number || Leetcode 1539 || Variant Question Big Tech Actually AsksCoding with Minmer · 19:12 · 8K views
Kth Missing Positive Number || Binary Search || 2-Pointers || Leetcode-1539Aryan Mittal · 16:38 · 7K views
LeetCode 1539. Kth Missing Positive Number - Interview Prep Ep 87Fisher Coder · 11:32 · 7K views
Kth Missing Positive Number | LeetCode 1539Learn Code Repeat · 14:09 · 6K views
1539. Kth Missing Positive Number | LeetCode Daily Challenge | LeetCode POTDDeep Tech · 13:26 · 2K views
The problem
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?
Approach overview
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.
Approach 1: Iterative Approach
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.
def findKthPositive(arr, k):
missing_count = 0
current = 1
i = 0
while missing_count < k:
if i < len(arr) and arr[i] == current:
i += 1
else:
missing_count += 1
if missing_count == k:
return current
current += 1
return -1 # this line is never reached
arr = [2, 3, 4, 7, 11]
k = 5
print(findKthPositive(arr, k))public class Solution {
public int findKthPositive(int[] arr, int k) {
int missing_count = 0;
int current = 1;
int i = 0;
while (missing_count < k) {
if (i < arr.length && arr[i] == current) {
i++;
} else {
missing_count++;
if (missing_count == k) return current;
}
current++;
}
return -1; // this line is never reached
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = {2, 3, 4, 7, 11};
System.out.println(solution.findKthPositive(arr, 5));
}
}#include <vector>
using namespace std;
int findKthPositive(vector<int>& arr, int k) {
int missing_count = 0;
int current = 1;
int i = 0;
while (missing_count < k) {
if (i < arr.size() && arr[i] == current) {
i++;
} else {
missing_count++;
if (missing_count == k) return current;
}
current++;
}
return -1; // this line is never reached
}
int main() {
vector<int> arr = {2, 3, 4, 7, 11};
int k = 5;
printf("%d\n", findKthPositive(arr, k));
return 0;
}function findKthPositive(arr, k) {
let missing_count = 0;
let current = 1;
let i = 0;
while (missing_count < k) {
if (i < arr.length && arr[i] === current) {
i++;
} else {
missing_count++;
if (missing_count === k) return current;
}
current++;
}
return -1; // this line is never reached
}
let arr = [2, 3, 4, 7, 11];
let k = 5;
console.log(findKthPositive(arr, k));#include <stdio.h>
int findKthPositive(int* arr, int arrSize, int k) {
int missing_count = 0;
int current = 1;
int i = 0;
while (missing_count < k) {
if (i < arrSize && arr[i] == current) {
i++;
} else {
missing_count++;
if (missing_count == k) return current;
}
current++;
}
return -1; // this line is never reached
}
int main() {
int arr[] = {2, 3, 4, 7, 11};
int k = 5;
printf("%d\n", findKthPositive(arr, 5, k));
return 0;
}public class Solution {
public int FindKthPositive(int[] arr, int k) {
int missing_count = 0;
int current = 1;
int i = 0;
while (missing_count < k) {
if (i < arr.Length && arr[i] == current) {
i++;
} else {
missing_count++;
if (missing_count == k) return current;
}
current++;
}
return -1; // this line is never reached
}
public static void Main(string[] args) {
int[] arr = {2, 3, 4, 7, 11};
Solution solution = new Solution();
Console.WriteLine(solution.FindKthPositive(arr, 5));
}
}This Python solution is straightforward and utilizes a while loop to track missing numbers. The logic is similar to that in C/C++/Java implementations, making it easy to follow along.
Time Complexity: O(n + k), Space Complexity: O(1).
Approach 2: Binary Search Optimization
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.
def findKthPositive(arr, k):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] - (mid + 1) < k:
left = mid + 1
else:
right = mid - 1
return left + k
arr = [2, 3, 4, 7, 11]
k = 5
print(findKthPositive(arr, k))public class Solution {
public int findKthPositive(int[] arr, int k) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] - (mid + 1) < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left + k;
}
public static void main(String[] args) {
int[] arr = {2, 3, 4, 7, 11};
Solution solution = new Solution();
System.out.println(solution.findKthPositive(arr, 5));
}
}#include <vector>
using namespace std;
int findKthPositive(vector<int>& arr, int k) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] - (mid + 1) < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left + k;
}
int main() {
vector<int> arr = {2, 3, 4, 7, 11};
int k = 5;
printf("%d\n", findKthPositive(arr, k));
return 0;
}function findKthPositive(arr, k) {
let left = 0, right = arr.length - 1;
while (left <= right) {
let mid = left + ((right - left) >> 1);
if (arr[mid] - (mid + 1) < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left + k;
}
let arr = [2, 3, 4, 7, 11];
let k = 5;
console.log(findKthPositive(arr, k));#include <stdio.h>
int findKthPositive(int* arr, int arrSize, int k) {
int left = 0, right = arrSize - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int missing = arr[mid] - (mid + 1);
if (missing < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left + k;
}
int main() {
int arr[] = {2, 3, 4, 7, 11};
int k = 5;
printf("%d\n", findKthPositive(arr, 5, k));
return 0;
}public class Solution {
public int FindKthPositive(int[] arr, int k) {
int left = 0, right = arr.Length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] - (mid + 1) < k) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left + k;
}
public static void Main(string[] args) {
int[] arr = {2, 3, 4, 7, 11};
Solution solution = new Solution();
Console.WriteLine(solution.FindKthPositive(arr, 5));
}
}The Python solution follows a similar binary search approach. It calculates the number of missing numbers up to each midpoint in the array and uses that to refine the search for the missing k-th integer.
Time Complexity: O(log n), Space Complexity: O(1).
Approach 3: Default Approach
func findKthPositive(arr []int, k int) int {
if arr[0] > k {
return k
}
left, right := 0, len(arr)
for 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)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n + k), Space Complexity: O(1). |
| Binary Search Optimization | Time Complexity: O(log n), Space Complexity: O(1). |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Kth Missing Positive Number easy or hard?
LeetCode classifies this problem as Easy. The iterative O(n) solution is straightforward once you understand how to compute missing numbers using arr[i] - (i + 1). The binary search optimization adds a moderate algorithmic twist but follows standard sorted-array search patterns.
Kth Missing Positive Number Python or Java solution?
Both Python and Java implementations follow the same logic. The iterative solution scans the array while tracking missing counts, while the binary search version repeatedly checks arr[mid] - (mid + 1) to locate the kth missing value in O(log n) time.
How to solve Kth Missing Positive Number in O(log n)?
Use binary search on the array to locate the first index where the number of missing values is at least k. The missing count before index i is arr[i] - (i + 1). Compare this value with k while adjusting the search range. Once the boundary is found, compute the exact kth missing value using the index and k.
What is the best approach for Kth Missing Positive Number?
Binary search is the most efficient approach because the array is sorted. By computing how many numbers are missing before each index using arr[i] - (i + 1), you can binary search for the first position where the missing count reaches k. This reduces the time complexity to O(log n) with constant extra space.
Is Kth Missing Positive Number asked at Google/Amazon/Meta?
Variations of this problem appear in interviews at companies like Amazon, Google, and Meta because it tests reasoning about sorted arrays and binary search boundaries. Candidates must recognize the mathematical relationship between indices and missing values.
What data structure is used in Kth Missing Positive Number?
The problem primarily uses arrays. The optimized solution also applies binary search on the array indices to exploit the monotonic increase of missing counts across the sorted sequence.
What is the time complexity of Kth Missing Positive Number?
Two common solutions exist. A straightforward iterative scan runs in O(n) time and O(1) space. The optimized binary search solution runs in O(log n) time and O(1) space by leveraging the sorted nature of the array.