#1539

Easy

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Kth Missing Positive Number

Find the kth missing positive integer in a strictly increasing array using binary search over the answer space efficiently.

array binary search

Problem Statement

Given a strictly increasing array of positive integers and an integer k, identify which positive integer is the kth one missing from the sequence. For example, arr = [2,3,4,7,11] with k = 5 should return 9, as the missing numbers are [1,5,6,8,9,...].

Return a single integer representing the kth missing positive number. Constraints ensure array length and values remain reasonable: 1 <= arr.length <= 1000, 1 <= arr[i] <= 1000, and 1 <= k <= 1000.

Examples

Example 1

Input: arr = [2,3,4,7,11], k = 5

Output: 9

The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2

Input: arr = [1,2,3,4], k = 2

Output: 6

The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Constraints

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

Solution Approach

Linear Scan with Missing Count

Iterate through the array, counting missing numbers between consecutive elements. Stop once the count reaches k and compute the exact missing value. This approach is simple but can be slower if k is large.

Binary Search Over Answer Space

Use binary search on the range of possible positive integers. At each midpoint, count how many numbers are missing before it using arr[i] - i - 1. Adjust search bounds until the kth missing number is identified. This is the optimal O(log n) approach.

Handling Edge Cases

If k exceeds all missing numbers within arr, calculate the missing number beyond the last element. Ensure indexes and counts are correctly managed to avoid off-by-one errors.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(log n) using binary search over the valid answer space, or O(n) for a linear scan. Space complexity is O(1) since no extra storage is required beyond counters and pointers.

What Interviewers Usually Probe

Ask for edge case handling when k exceeds the last array element.
Probe understanding of how to count missing numbers efficiently at each index.
Test whether candidate can implement binary search over a value range, not just array indices.

Common Pitfalls or Variants

Common pitfalls

Miscounting missing numbers leading to off-by-one errors.
Failing to handle cases where kth missing number is larger than the array's last element.
Confusing array indices with actual values when computing missing counts.

Follow-up variants

Find the kth missing positive number in an unsorted array, requiring sorting first.
Return the list of the first k missing positive numbers instead of only the kth.
Find the kth missing number where array contains duplicates, requiring deduplication.

FAQ

What is the optimal approach to solve Kth Missing Positive Number?

Binary search over the valid answer space is optimal, counting missing numbers before each midpoint to locate the kth missing integer.

Can I use a linear scan for this problem?

Yes, a linear scan works but is less efficient for large k compared to the binary search method.

How do I handle k exceeding all missing numbers in arr?

Compute the missing number beyond the last array element by adding the difference between k and total missing numbers so far.

Why is arr[i] - i - 1 used in counting missing numbers?

This formula calculates how many positive numbers are missing before arr[i], considering the index offset.

Does this problem always require sorted arrays?

Yes, the binary search approach relies on a strictly increasing sorted array to correctly count missing numbers.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        if arr[0] > k:
            return k
        left, right = 0, len(arr)
        while left < right:
            mid = (left + right) >> 1
            if arr[mid] - mid - 1 >= k:
                right = mid
            else:
                left = mid + 1
        return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1)

Continue Practicing

#1552 magnetic force between two balls #1521 find a value of a mysterious function closest to target #1562 find latest group of size m