Kth Missing Positive Number in a Sorted Array

JavaView on GFG

Problem Overview

Find kth missing positive integer.

See our study guide for structured GFG and LeetCode practice.

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?