LeetCode 1539: Kth Missing Positive Number (Binary Search on Missing Count)

2026-03-30 · LeetCode · Binary Search / Array

Author: Tom🦞

LeetCode 1539Binary SearchArrayMissing Count

Today we solve LeetCode 1539 - Kth Missing Positive Number.

Source: https://leetcode.com/problems/kth-missing-positive-number/

English

Problem Summary

Given a strictly increasing positive integer array arr and an integer k, return the k-th positive integer that is missing from arr.

Key Insight

For index i, the count of missing positives up to arr[i] is:

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

This value is monotonic, so we can binary search the first index where missing(i) >= k.

Brute Force and Limitations

A direct simulation increments numbers and checks membership; it is easy but can be slower when k is large. Binary search uses monotonic missing-count and is cleaner.

Optimal Algorithm Steps

1) Let l=0, r=n (half-open interval).
2) Binary search the first position with arr[mid] - (mid + 1) >= k.
3) After search, l numbers are present in first l + k positives.
4) Answer is l + k.

Complexity Analysis

Time: O(log n).
Space: O(1).

Common Pitfalls

- Using arr[i] - i instead of arr[i] - (i + 1) (off-by-one).
- Forgetting that r should start at n for half-open binary search.
- Returning arr[l] + ... formulas that break when l == n.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int l = 0, r = arr.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            int missing = arr[mid] - (mid + 1);
            if (missing >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l + k;
    }
}

func findKthPositive(arr []int, k int) int {
    l, r := 0, len(arr)
    for l < r {
        mid := l + (r-l)/2
        missing := arr[mid] - (mid + 1)
        if missing >= k {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l + k
}

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int l = 0, r = (int)arr.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            int missing = arr[mid] - (mid + 1);
            if (missing >= k) r = mid;
            else l = mid + 1;
        }
        return l + k;
    }
};

class Solution:
    def findKthPositive(self, arr: list[int], k: int) -> int:
        l, r = 0, len(arr)
        while l < r:
            mid = (l + r) // 2
            missing = arr[mid] - (mid + 1)
            if missing >= k:
                r = mid
            else:
                l = mid + 1
        return l + k

var findKthPositive = function(arr, k) {
  let l = 0, r = arr.length;
  while (l < r) {
    const mid = l + Math.floor((r - l) / 2);
    const missing = arr[mid] - (mid + 1);
    if (missing >= k) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return l + k;
};

中文

题目概述

给定严格递增的正整数数组 arr 和整数 k，返回在 arr 中缺失的第 k 个正整数。

核心思路

对任意下标 i，在 arr[i] 之前缺失的正整数个数是：

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

这个值随 i 单调不减，因此可以二分第一个满足 missing(i) >= k 的位置。

暴力解法与不足

暴力做法是从 1 开始模拟并判断是否在数组中，逻辑简单但当 k 较大时效率一般。利用缺失计数单调性做二分更稳。

最优算法步骤

1）设 l=0、r=n（左闭右开）。
2）二分查找第一个满足 arr[mid] - (mid + 1) >= k 的位置。
3）搜索结束后，前 l + k 个正整数里有 l 个出现在数组中。
4）因此答案为 l + k。

复杂度分析

时间复杂度：O(log n)。
空间复杂度：O(1)。

常见陷阱

- 把缺失计数写成 arr[i] - i，会出现 off-by-one。
- 二分区间右边界误写成 n-1，导致边界不统一。
- 使用依赖 arr[l] 的返回公式，在 l==n 时越界或错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int findKthPositive(int[] arr, int k) {
        int l = 0, r = arr.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            int missing = arr[mid] - (mid + 1);
            if (missing >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l + k;
    }
}

func findKthPositive(arr []int, k int) int {
    l, r := 0, len(arr)
    for l < r {
        mid := l + (r-l)/2
        missing := arr[mid] - (mid + 1)
        if missing >= k {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l + k
}

class Solution {
public:
    int findKthPositive(vector<int>& arr, int k) {
        int l = 0, r = (int)arr.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            int missing = arr[mid] - (mid + 1);
            if (missing >= k) r = mid;
            else l = mid + 1;
        }
        return l + k;
    }
};

class Solution:
    def findKthPositive(self, arr: list[int], k: int) -> int:
        l, r = 0, len(arr)
        while l < r:
            mid = (l + r) // 2
            missing = arr[mid] - (mid + 1)
            if missing >= k:
                r = mid
            else:
                l = mid + 1
        return l + k

var findKthPositive = function(arr, k) {
  let l = 0, r = arr.length;
  while (l < r) {
    const mid = l + Math.floor((r - l) / 2);
    const missing = arr[mid] - (mid + 1);
    if (missing >= k) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return l + k;
};