Kth Missing Positive Number — Easy Problem & Solution

Problem statement

arr is a strictly increasing array of positive integers.

Return the k-th positive integer that is missing from arr.

Example 1

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing numbers are 1, 5, 6, 8, 9, 10, …

Example 2

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: Nothing is missing below 5, so the missing run starts at 5.

Example 3

Input: arr = [5], k = 3
Output: 3

Constraints

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000
• 1 <= k <= 1000
• arr is strictly increasing.

How to solve Kth Missing Positive Number

Define missing(i) = arr[i] - (i + 1), the number of absent positives strictly below arr[i]. It is non-decreasing, so binary search finds the boundary where it first reaches k, and simple arithmetic recovers the answer.

Approach

1. Binary search over [0, n] for the first index with missing(mid) >= k.
2. Let lo be that boundary — every index before it has fewer than k missing numbers.
3. Return lo + k.

Why it works

Below index lo, the array covers lo of the positives and hides missing(lo-1) < k of them, so the k-th missing number lies in the gap starting at arr[lo-1] + 1 — equivalently at lo + k, since the first lo array entries occupy lo slots. When the whole array has fewer than k missing numbers, lo = n and n + k is right for the same reason.

Complexity

• Time — O(log n)
• Space — O(1)

Pitfalls

• The linear scan is fine at n = 1000 but the formula is what generalises.
• missing(i) uses i + 1, not i — the array is 0-indexed but counts from 1.
• The k-th missing number can exceed every element of arr.

Reference solution

Python

from typing import List

def findKthPositive(arr: List[int], k: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] - (mid + 1) < k:
            lo = mid + 1
        else:
            hi = mid
    return lo + k

JavaScript

var findKthPositive = function(arr, k) {
    var lo = 0, hi = arr.length;
    while (lo < hi) {
        var mid = (lo + hi) >> 1;
        if (arr[mid] - (mid + 1) < k) lo = mid + 1; else hi = mid;
    }
    return lo + k;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Special Array I Easy
• Type of Triangle Easy
• Find the Losers of the Circular Game Easy
• Form Smallest Number From Two Digit Arrays Easy
• Delete Greatest Value in Each Row Easy
• The Employee That Worked on the Longest Task Easy