Kth Missing Positive Number in a Sorted Array

JavaView on GFG

Intuition

Find kth missing positive integer. Binary search on index: missing before index i = arr[i]-i-1.

Algorithm

1Binary search: if arr[mid]-mid-1 < k: lo=mid+1. Else hi=mid-1. Answer = lo+k.

Common Pitfalls

•Same as LC 1539. Missing count before index i = arr[i]-(i+1). Binary search for split point.

Kth Missing Positive Number in a Sorted Array.java

Java

// Approach: Binary search. For index i, missing count = arr[i] - (i+1). Find where missing count >= k.
// Time: O(log n) Space: O(1)
class Solution {
    public int kthMissing(int[] arr, int k) {
        // checking inside array
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] <= k)
                k++;
            else
                break;
        }
        return k;
    }
}

Was this solution helpful?