Find Kth Missing Positive Number in Sorted Array Binary Search Approach

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

You're given a sorted array of unique positive integers and an integer k. The array is strictly increasing, but it may be missing some positive numbers. Your task is to find the kth missing positive number in the sequence.

The array only contains some of the positive integers starting from 1, and some numbers are missing. You must figure out what the kth missing number would be if we continued counting all the positive numbers in order.

If the array is empty, then the answer is simply k because all numbers are missing.

Examples❯

Input Array k Output Description
[2, 3, 4, 7, 11] 5 9 Missing numbers: [1, 5, 6, 8, 9, 10], 5th one is 9
[1, 2, 3, 4] 2 6 No missing until 4, missing numbers are [5, 6], 2nd is 6
[1, 3, 5, 10] 4 6 Missing: [2, 4, 6, 7, 8, 9], 4th one is 6
[2, 3, 4] 1 1 1 is missing before array starts
[10, 11, 12] 3 3 Missing: [1, 2, 3, 4...], 3rd one is 3
[1, 2, 3, 4] 0 0 No missing required
[] 4 4 Empty array: all numbers are missing, return k = 4
[2] 1 1 1 is missing before the first element
[5] 2 2 Missing: [1, 2, 3, 4], 2nd is 2

Solution❯

Understanding the Problem

We are given a sorted array of distinct positive integers, and we are asked to find the kth missing positive number.

To put it simply, we need to simulate counting from 1 upwards and identify which positive numbers are not present in the array. The kth number among those missing is our answer.

For example, consider the array [2, 3, 4, 7, 11] and k = 5. The missing numbers are [1, 5, 6, 8, 9, 10], so the 5th missing number is 9.

Step-by-Step Solution with Example

step 1: Identify expected and actual values

At index i, the expected value is i + 1 if all numbers were present. But the actual value is arr[i]. So the total number of missing values up to index i is:

missingCount = arr[i] - (i + 1)

step 2: Iterate or use binary search

We traverse the array and for each index, calculate how many numbers are missing so far. If missingCount < k, we move forward. When we find the first index where missingCount ≥ k, we know the missing number lies before arr[i].

step 3: Use the previous value and compute the answer

If missingCount becomes ≥ k at index i, we use:

arr[i - 1] + (k - missingBeforePrevious)

This finds how many numbers we still need to add after the previous element to reach the kth missing.

step 4: Handle the case when all missing numbers are after the array ends

If the entire array is not missing enough values, the missing numbers are beyond the last element. Then the answer is:

arr[n - 1] + (k - totalMissing)

Example: arr = [2, 3, 4, 7, 11], k = 5


Index  Value  MissingCount
0      2      1 (1 is missing)
1      3      1 (no new missing)
2      4      1 (no new missing)
3      7      3 (5 and 6 are missing)
4      11     6 (8, 9, 10 are also missing)

At index 4, missing count is 6 ≥ 5, so kth missing lies before 11.
Previous value = 7, previous missing = 3
Still need 5 - 3 = 2 more steps → 7 + 2 = 9

Answer: 9

Edge Cases

  • Array starts after 1: If the array starts from a number > 1, initial values are missing (e.g., [4, 5] → missing = [1, 2, 3])
  • Array has no gaps: If array is like [1, 2, 3], the missing values begin after the end → kth missing = last + k
  • Empty array: If the array is empty, kth missing = k itself
  • k is small: Often the missing number lies before any actual gap. Be sure to check the first element.

Finally

This problem teaches us how to track missing values efficiently using either a loop or binary search. The key insight is to compare the expected count of numbers versus the actual values in the array. With this, we can find the exact position of the kth missing number without simulating the entire sequence.

Binary search gives us an efficient solution for large arrays with O(log n) time complexity, while linear scan also works fine for small inputs.

Algorithm Steps❯

  1. Initialize low = 0 and high = arr.length - 1.
  2. While low ≤ high:
  3. → Calculate mid = low + (high - low) / 2.
  4. → Compute missing = arr[mid] - (mid + 1).
  5. → If missing < k, search right side by setting low = mid + 1.
  6. → Else, search left side by setting high = mid - 1.
  7. Finally, return low + k as the answer.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int findKthPositive(int* arr, int n, int k) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int missing = arr[mid] - (mid + 1);
        if (missing < k)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return low + k;
}

int main() {
    int arr[] = {2, 3, 4, 7, 11};
    int k = 5;
    printf("Kth missing number is: %d\n", findKthPositive(arr, 5, k));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(1)The target is found in the first binary search step.
Average CaseO(log n)Binary search halves the search space at each step, making it efficient even for large arrays.
Worst CaseO(log n)At most, the search checks log(n) elements until the missing count reaches or exceeds k.

Space Complexity❯

O(1)

Explanation: The algorithm only uses a constant number of variables regardless of input size.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...