Kth Missing Positive Number

Easy
810.

Kth Missing Positive Number

Kth Missing Positive Number is an easy coding problem on arrays and binary search, asked in Amazon, Google and Accenture interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var findKthPositive = function(arr, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Kth Missing Positive Number — Solution in Python, Java & C++

Kth Missing Positive Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Kth Missing Positive Number is an easy coding problem on arrays and binary search, asked in Amazon, Google and Accenture interviews.

  • Difficulty: Easy
  • Topics: Arrays, Binary Search
  • Asked at: Amazon, Google, Accenture
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Kth Missing Positive Number

  1. Hint 1

    At index i, exactly arr[i] - (i + 1) positive integers are missing before arr[i].

  2. Hint 2

    That quantity is non-decreasing in i, so binary search applies.

  3. Hint 3

    Find the first index where the missing count reaches k; the answer is that index plus k.

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

Java

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

C++

int findKthPositive(vector<int>& arr, int k) {
    int lo = 0, hi = (int) arr.size();
    while (lo < hi) {
        int 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search