Find the Kth Positive Integer Missing From a Sorted Array
Solve this Problemarr and an integer k, find the k-th positive integer that does not appear in the array.
Every position in the array hides a count: at index i (0-indexed), if no positive integer were missing, arr[i] would equal i + 1 exactly. The gap between them — arr[i] - (i + 1) — is exactly how many positive integers are missing among the first i + 1 array slots. That gap only ever grows (or stays flat) moving rightward through the array, which makes this a binary search on the answerBinary Search on the AnswerThe search runs directly over the space of candidate answers rather than over the array's values. It applies whenever a derived quantity — here, the count of missing numbers so far — only ever increases (or only decreases) as the search position moves in one direction.: binary search finds the boundary index where the missing count first reaches k, and the answer follows directly from that boundary.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ length of arr ≤ 1000 - ◆
arr is sorted in strictly increasing order - ◆
1 ≤ arr[i] ≤ 1000 - ◆
1 ≤ k ≤ 1000
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Walk the Positive Integers One at a Time
BruteWalk candidate = 1, 2, 3, ... alongside a pointer into arr. If the pointer's current array value equals the candidate, that candidate is present, so advance the pointer and move on. Otherwise the candidate is missing — count it down from k, and once k reaches 0 the current candidate is the answer. Correct and easy to follow, but it revisits every integer up to the answer one at a time instead of jumping straight there.
O(n + k)O(1)1class Solution {
2 public int kthMissingPositive(int[] arr, int k) {
3 int candidate = 1, ptr = 0;
4 while (true) {
5 if (ptr < arr.length && arr[ptr] == candidate) {
6 ptr++;
7 } else {
8 k--;
9 if (k == 0) return candidate;
10 }
11 candidate++;
12 }
13 }
14}Optimal — Binary Search on the Missing Count
OptimalAt index i (0-indexed), if nothing were missing, arr[i] would equal i + 1 — so arr[i] - (i + 1) is exactly how many positive integers are missing among the first i + 1 slots. That missing count only ever grows (or stays flat) moving right through the array, so binary search can find the boundary index where the missing count first reaches k. Past that boundary (lo, after the loop), the answer is simply lo + k — lo positions have already been "used up" by present values, so the kth missing integer is k steps past them.
O(log n)O(1)1class Solution {
2 public int kthMissingPositive(int[] arr, int k) {
3 int lo = 0, hi = arr.length - 1;
4 while (lo <= hi) {
5 int mid = lo + (hi - lo) / 2;
6 int missing = arr[mid] - (mid + 1);
7 if (missing < k) {
8 lo = mid + 1;
9 } else {
10 hi = mid - 1;
11 }
12 }
13 return lo + k;
14 }
15}