Kth - missing positive number

Problem Link

kth-missing-positive-number

Problem Statement

You are given a sorted array arr of positive integers in strictly increasing order, and an integer k.

Your task is to return the k-th positive integer that is missing from the array.

Examples

• Input: arr = [2, 3, 4, 7, 11], k = 5
  Output: 9
  Explanation: Missing numbers = [1, 5, 6, 8, 9, 10, 12, ...].
  The 5th missing number is 9.

• Input: arr = [1, 2, 3, 4], k = 2
  Output: 6
  Explanation: Missing numbers = [5, 6, 7, ...].
  The 2nd missing number is 6.

Constraints

• 1 <= arr.length <= 1000

• 1 <= arr[i] <= 1000

• 1 <= k <= 1000

• arr[i] < arr[j] for all valid i < j

Intuition

In a perfect sequence of positive integers [1, 2, 3, ...], the i-th index would have the value i + 1.

But since elements are missing in arr, the number of missing elements before index i is:

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

We want to find the first position i such that the number of missing integers before it is at least k.

This makes it suitable for binary search.

Approach (Binary Search)

1. Initialize search boundaries: start = 0, end = arr.length - 1

2. While start <= end:

   • Compute mid = start + (end - start) / 2

   • Calculate how many numbers are missing before mid:

     missing = arr[mid] - (mid + 1)
     

   • If missing < k, move right → start = mid + 1

   • Else, move left → end = mid - 1

3. After the loop ends, the answer is:

   start + k
   

Java Code

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            int missing = arr[mid] - (mid + 1);
            if (missing < k) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return start + k;
    }
}

Time and Space Complexity

• Time Complexity: O(log n)
  Efficient binary search over the array.

• Space Complexity: O(1)
  No extra data structures used.

Dry Run

Input:

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

Iterations:

• start = 0, end = 4

• mid = 2, arr[2] = 4, missing = 4 - (2 + 1) = 1 → 1 < 5 → move right → start = 3

• mid = 3, arr[3] = 7, missing = 7 - (3 + 1) = 3 → 3 < 5 → move right → start = 4

• mid = 4, arr[4] = 11, missing = 11 - (4 + 1) = 6 → 6 >= 5 → move left → end = 3

Loop ends: start = 4, so answer = 4 + 5 = 9

Output: 9

Conclusion

This problem showcases a smart application of binary search over virtual properties of a sequence (in this case, the number of missing elements). The trick lies in calculating how many numbers are missing up to any given index and narrowing the search accordingly.

This technique is powerful for problems involving gaps or differences in expected versus actual sequences.