Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Kth Missing Positive Number

EASYProblemSolveExternal Links

Description

Given an array arr of positive integers sorted in strictly increasing order and a positive integer k, return the kth positive integer that is missing from the array.

A positive integer is "missing" if it does not appear in arr. The missing integers are counted starting from 1 upward. For example, if arr = [2, 3, 4, 7, 11], then the missing positive integers in order are 1, 5, 6, 8, 9, 10, 12, 13, ...

Your task is to find the kth number in that sequence of missing values.

Examples

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, ...]. The 5th missing positive integer is 9.

Example 2

Input: arr = [1, 2, 3, 4], k = 2

Output: 6

Explanation: The array contains 1, 2, 3, 4 with no gaps. The missing positive integers start after the array: [5, 6, 7, ...]. The 2nd missing positive integer is 6.

Example 3

Input: arr = [5, 6, 7, 8], k = 3

Output: 3

Explanation: The numbers 1, 2, 3, 4 are all missing before the array even starts. The 3rd missing positive integer is 3.

Constraints

  • 1 ≤ arr.length ≤ 1000
  • 1 ≤ arr[i] ≤ 1000
  • 1 ≤ k ≤ 1000
  • arr[i] < arr[i + 1] for all valid i (strictly increasing)

Editorial

Brute Force

Intuition

The most direct approach is to walk through the array and count how many positive integers are missing as we go. The key idea: if no numbers were missing, arr[0] would be 1, arr[1] would be 2, and so on. Any element larger than its expected value means some numbers were skipped.

We iterate through the array and ask: for each element, does it fall within the range of our target? If arr[i] is less than or equal to our current target k, it means this element is a present number that pushes the kth missing number further out. So we increment k by 1.

Think of it this way: imagine you are counting missing numbers starting from 1. The kth missing would be simply k if no array elements existed. But each array element that is ≤ k "occupies" a spot in the number line that is not missing, pushing your answer forward by one.

Step-by-Step Explanation

Let's trace through with arr = [2, 3, 4, 7, 11], k = 5:

The idea: traverse the array. If arr[i] ≤ k, this element occupies a position in the positive integers, pushing the kth missing number further out. Increment k.

Step 1: i = 0, arr[0] = 2. Is 2 ≤ 5? Yes. This means the number 2 is present, so the kth missing is now shifted by 1. Update k = 6.

Step 2: i = 1, arr[1] = 3. Is 3 ≤ 6? Yes. Number 3 is present, push the target further. Update k = 7.

Step 3: i = 2, arr[2] = 4. Is 4 ≤ 7? Yes. Number 4 is present. Update k = 8.

Step 4: i = 3, arr[3] = 7. Is 7 ≤ 8? Yes. Number 7 is present. Update k = 9.

Step 5: i = 4, arr[4] = 11. Is 11 ≤ 9? No. We stop here. The array element 11 is past our target, so the kth missing number is k = 9.

Step 6: Return k = 9.

Verification: Missing positives are [1, 5, 6, 8, 9]. The 5th is indeed 9. ✓

Brute Force — Shifting k Past Present Elements — Watch how each array element that falls within our search range pushes k forward by one, until an element exceeds k, revealing the answer.

Algorithm

  1. Iterate through each element in arr:
    • If arr[i] ≤ k, increment k by 1 (this element occupies a position, pushing the target further)
    • Otherwise, stop (the kth missing number is before this element)
  2. Return k

Code

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        for (int i = 0; i < arr.size(); i++) {
            if (arr[i] <= k) {
                k++;
            } else {
                break;
            }
        }
        return k;
    }
};
class Solution:
    def findKthPositive(self, arr: list[int], k: int) -> int:
        for num in arr:
            if num <= k:
                k += 1
            else:
                break
        return k
class Solution {
    public int findKthPositive(int[] arr, int k) {
        for (int num : arr) {
            if (num <= k) {
                k++;
            } else {
                break;
            }
        }
        return k;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the array once. In the worst case (when all elements are within range), we check every element before returning. Each check is O(1), so the total time is O(n) where n is the length of the array.

Space Complexity: O(1)

We only modify the variable k in place and use no extra data structures.

Why This Approach Is Not Efficient

The brute force scans through every element of the array one by one. With n elements, this takes O(n) time in the worst case.

However, we can do better. The critical insight is that the number of missing positive integers before any position i in the array can be computed directly with a formula: missing_count = arr[i] - (i + 1). If no numbers were missing, arr[i] would equal i + 1. The difference tells us exactly how many are missing.

Since the array is sorted and the missing count is monotonically non-decreasing, we can binary search for the position where the missing count first reaches or exceeds k. This reduces the time from O(n) to O(log n).

For example, with arr = [2, 3, 4, 7, 11], the missing counts are:

  • Index 0: 2 - 1 = 1 missing
  • Index 1: 3 - 2 = 1 missing
  • Index 2: 4 - 3 = 1 missing
  • Index 3: 7 - 4 = 3 missing
  • Index 4: 11 - 5 = 6 missing

Instead of scanning all 5 elements, binary search finds the transition point in just 3 comparisons.

Optimal Approach - Binary Search

Intuition

The foundation of this approach is a simple but powerful formula: at any index i in the array, the number of positive integers missing before arr[i] is:

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

Why does this work? If no numbers were missing, the element at index 0 would be 1, at index 1 would be 2, and so on — generally arr[i] would equal i + 1. The actual value arr[i] minus the ideal value i + 1 gives us exactly how many numbers were skipped.

Since the array is strictly increasing, missing_before(i) is a non-decreasing function. This is the key property that makes binary search applicable. We are searching for the rightmost index where missing_before(i) < k — or equivalently, the leftmost index where missing_before(i) ≥ k.

Once we find this boundary:

  • All elements to the left of it have fewer than k missing numbers before them.
  • The element at the boundary (or beyond) has at least k missing numbers before it.

The kth missing number must lie just after the element at position left - 1. After the binary search loop terminates, the answer simplifies elegantly to left + k. This works because left counts how many array elements appear before the kth missing number, and adding k to that gives the actual value of the kth missing positive integer.

Table showing array values, ideal values, and missing counts at each index for arr = [2, 3, 4, 7, 11]
Table showing array values, ideal values, and missing counts at each index for arr = [2, 3, 4, 7, 11]

Step-by-Step Explanation

Let's trace through with arr = [2, 3, 4, 7, 11], k = 5:

Step 1: Initialize left = 0, right = 4 (last index).

Step 2: Compute mid = (0 + 4) / 2 = 2. Calculate missing_before(2) = arr[2] - (2 + 1) = 4 - 3 = 1.

  • Is 1 ≥ 5? No. Fewer than k numbers are missing before index 2. The answer must be to the right.
  • Update: left = mid + 1 = 3.

Step 3: Compute mid = (3 + 4) / 2 = 3. Calculate missing_before(3) = arr[3] - (3 + 1) = 7 - 4 = 3.

  • Is 3 ≥ 5? No. Still not enough missing numbers. Move right.
  • Update: left = mid + 1 = 4.

Step 4: Compute mid = (4 + 4) / 2 = 4. Calculate missing_before(4) = arr[4] - (4 + 1) = 11 - 5 = 6.

  • Is 6 ≥ 5? Yes! At least k numbers are missing before index 4. The answer might be here or to the left.
  • Update: right = mid - 1 = 3.

Step 5: Now left = 4 > right = 3. Loop ends. The answer is left + k = 4 + 5 = 9.

Step 6: Return 9. Verify: missing = [1, 5, 6, 8, 9]. The 5th is 9. ✓

Binary Search for Kth Missing — Using the Missing Count Formula — Watch how binary search uses the formula arr[mid] - (mid+1) to count missing numbers at each midpoint, halving the search space until the boundary is found.

Algorithm

  1. Initialize left = 0 and right = n - 1
  2. While left ≤ right:
    • Compute mid = (left + right) / 2
    • Calculate missing = arr[mid] - (mid + 1)
    • If missing < k, the kth missing number is to the right → set left = mid + 1
    • Otherwise (missing ≥ k), it could be at this position or to the left → set right = mid - 1
  3. After the loop, return left + k
    • This works because left represents how many array elements appear before the kth missing number, and k itself accounts for the missing count.

Code

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int left = 0, right = arr.size() - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // Number of missing positives before arr[mid]
            int missing = arr[mid] - (mid + 1);
            
            if (missing < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // left + k gives the kth missing positive
        return left + k;
    }
};
class Solution:
    def findKthPositive(self, arr: list[int], k: int) -> int:
        left, right = 0, len(arr) - 1
        
        while left <= right:
            mid = (left + right) // 2
            # Number of missing positives before arr[mid]
            missing = arr[mid] - (mid + 1)
            
            if missing < k:
                left = mid + 1
            else:
                right = mid - 1
        
        # left + k gives the kth missing positive
        return left + k
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;
            // Number of missing positives before arr[mid]
            int missing = arr[mid] - (mid + 1);
            
            if (missing < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // left + k gives the kth missing positive
        return left + k;
    }
}

Complexity Analysis

Time Complexity: O(log n)

The binary search halves the search space with each iteration. Starting with n elements, the loop runs at most log₂(n) times. Each iteration performs O(1) arithmetic and comparisons, giving O(log n) total time.

Space Complexity: O(1)

We use only a constant number of integer variables (left, right, mid, missing). No additional arrays or data structures are allocated.