LeetCode 1539 - Kth Missing Positive Number

LeetCode Problem 1539

Difficulty: 🟢 Easy
Topics: Array, Binary Search

Solution

Problem Understanding

The problem gives us a strictly increasing array of positive integers, arr, and an integer k. The array does not necessarily contain every positive integer. Some numbers are missing from the natural sequence starting at 1.

Our task is to determine the kth positive integer that does not appear in the array.

For example, if the array is [2,3,4,7,11], then the missing positive integers are:

1, 5, 6, 8, 9, 10, 12, ...

The 5th missing number is 9, so the answer is 9.

The important detail is that the array is already sorted in strictly increasing order. This property allows us to reason about how many numbers are missing before a given index, which leads to an efficient binary search solution.

The constraints are relatively small:

• arr.length <= 1000
• arr[i] <= 1000
• k <= 1000

A straightforward linear scan would already work comfortably within these limits. However, the follow-up explicitly asks whether we can do better than O(n), which strongly hints that a binary search approach is expected.

Several edge cases are important:

• Missing numbers may start before the first array element. For example, if arr = [5,6,7], then 1,2,3,4 are all missing.
• The kth missing number may lie beyond the last element of the array. For example, arr = [1,2,3,4], k = 2 gives answer 6.
• The array may already begin with 1, meaning there are no missing numbers initially.
• The array length can be as small as 1, so the implementation must correctly handle very small inputs.

Approaches

Brute Force Approach

The most direct solution is to simulate the sequence of positive integers starting from 1.

We maintain:

• A pointer into the array
• A current number being checked
• A counter for how many missing numbers we have seen

For every positive integer:

• If it matches the current array element, we move the array pointer forward.
• Otherwise, the number is missing, so we increment the missing counter.
• Once the missing counter reaches k, we return the current number.

This works because we explicitly examine numbers in increasing order and count exactly which values are absent from the array.

Although correct, this approach is not optimal because it may require scanning many integers one by one.

Optimal Observation

The key insight is that we can determine how many numbers are missing before any array index.

Suppose we are at index i.

If no numbers were missing, the value at index i should be:

i + 1

because arrays are zero-indexed.

Instead, the actual value is:

arr[i]

Therefore, the number of missing integers before index i is:

arr[i] - (i + 1)

For example:

Index	Value	Expected	Missing Count
0	2	1	1
1	3	2	1
2	4	3	1
3	7	4	3

This missing count increases monotonically, which makes binary search possible.

We can binary search for the first index where the number of missing integers is at least k.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n + k)	O(1)	Simulates positive integers one by one
Optimal	O(log n)	O(1)	Uses binary search on missing counts

Algorithm Walkthrough

Optimal Binary Search Algorithm

1. Define a helper concept for the number of missing integers before index i.

The formula is:

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

This tells us how many positive integers are absent before arr[i]. 2. Initialize binary search boundaries.

Set:

• left = 0
• right = len(arr) - 1

We will search for the first position where the missing count becomes at least k. 3. Perform binary search.

While left <= right:

• Compute mid
• Compute missing = arr[mid] - (mid + 1)

If missing < k, then the kth missing number must lie further to the right, so move:

left = mid + 1

Otherwise, enough numbers are already missing by this point, so move:

right = mid - 1

4. Interpret the final position.

After binary search:

• left represents how many array elements are smaller than the kth missing number.
• The answer becomes:

left + k

5. Return the result.

Why it works

The binary search works because the missing count:

arr[i] - (i + 1)

is monotonically increasing.

As array values grow larger, the number of skipped integers can only stay the same or increase. This monotonic property guarantees that binary search can correctly locate the boundary where the missing count first reaches k.

Once we know how many array elements occur before the answer, the formula:

left + k

correctly reconstructs the kth missing positive integer.

Python Solution

from typing import List

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        left = 0
        right = len(arr) - 1

        while left <= right:
            mid = (left + right) // 2

            missing_count = arr[mid] - (mid + 1)

            if missing_count < k:
                left = mid + 1
            else:
                right = mid - 1

        return left + k

The implementation begins by setting up standard binary search boundaries over the array indices.

Inside the loop, we compute the midpoint and determine how many positive integers are missing before arr[mid].

If fewer than k numbers are missing so far, then the answer must appear after this index, so we move the left boundary forward.

Otherwise, the kth missing number is either at this position or earlier, so we move the right boundary backward.

After the loop finishes, left represents the number of array elements that appear before the kth missing number. Adding k gives the exact answer.

The solution uses only constant extra memory and performs logarithmic-time searching.

Go Solution

func findKthPositive(arr []int, k int) int {
	left := 0
	right := len(arr) - 1

	for left <= right {
		mid := left + (right-left)/2

		missingCount := arr[mid] - (mid + 1)

		if missingCount < k {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return left + k
}

The Go implementation follows the exact same logic as the Python version.

Slices in Go already provide efficient indexed access, so no additional data structures are needed.

The midpoint calculation uses:

left + (right-left)/2

which is the standard overflow-safe binary search pattern, although overflow is not a concern under these constraints.

The algorithm uses constant extra space and handles all edge cases naturally.

Worked Examples

Example 1

Input:

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

First compute missing counts:

Index	Value	Missing Count
0	2	1
1	3	1
2	4	1
3	7	3
4	11	6

We binary search for the first index where missing count is at least 5.

Step	left	right	mid	arr[mid]	missing_count	Action
1	0	4	2	4	1	move left
2	3	4	3	7	3	move left
3	4	4	4	11	6	move right

Loop ends with:

left = 4

Answer:

left + k = 4 + 5 = 9

Final answer:

9

Example 2

Input:

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

Missing counts:

Index	Value	Missing Count
0	1	0
1	2	0
2	3	0
3	4	0

Binary search:

Step	left	right	mid	missing_count	Action
1	0	3	1	0	move left
2	2	3	2	0	move left
3	3	3	3	0	move left

Loop ends with:

left = 4

Answer:

left + k = 4 + 2 = 6

Final answer:

6

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log n)	Binary search halves the search space each iteration
Space	O(1)	Only a few variables are used

The binary search performs at most log n iterations because the search interval is cut in half every step. No auxiliary data structures are allocated, so the extra space usage remains constant.

Test Cases

solution = Solution()

assert solution.findKthPositive([2, 3, 4, 7, 11], 5) == 9
# Standard example with missing numbers throughout

assert solution.findKthPositive([1, 2, 3, 4], 2) == 6
# Missing numbers occur after the array ends

assert solution.findKthPositive([5, 6, 7], 1) == 1
# Missing numbers begin before the first element

assert solution.findKthPositive([5, 6, 7], 4) == 4
# kth missing number still before first array element

assert solution.findKthPositive([1], 1) == 2
# Single-element array starting at 1

assert solution.findKthPositive([2], 1) == 1
# Smallest possible missing number

assert solution.findKthPositive([2], 5) == 6
# Answer extends beyond array

assert solution.findKthPositive([1, 10, 21, 22, 25], 12) == 15
# Large gaps inside array

assert solution.findKthPositive([3, 4, 5, 6], 2) == 2
# Multiple missing values before first element

assert solution.findKthPositive([1, 3], 1) == 2
# Single missing value inside array

Test Summary

Test	Why
[2,3,4,7,11], k=5	Standard mixed-gap example
[1,2,3,4], k=2	Missing numbers occur after array end
[5,6,7], k=1	First missing number before array
[5,6,7], k=4	Entire answer before first element
[1], k=1	Smallest valid array beginning at 1
[2], k=1	Smallest missing positive integer
[2], k=5	Answer larger than all array values
[1,10,21,22,25], k=12	Large internal gaps
[3,4,5,6], k=2	Consecutive missing prefix
[1,3], k=1	Single missing value in middle

Edge Cases

One important edge case occurs when the missing numbers begin before the first array element. For example, with arr = [5,6,7], the numbers 1,2,3,4 are all missing. A naive implementation that only checks gaps inside the array might overlook these missing prefix values. The binary search solution handles this naturally because the missing count formula correctly captures how many numbers are absent before each index.

Another critical edge case happens when the kth missing number lies beyond the end of the array. For example, arr = [1,2,3,4] and k = 2 produces answer 6. Some implementations incorrectly stop once they finish scanning the array. The formula left + k automatically extends beyond the array boundary when needed.

A third edge case involves very small arrays, especially arrays of length one. For example:

• arr = [1], k = 1
• arr = [2], k = 1

These cases can expose off-by-one mistakes in missing count calculations. The formula:

arr[i] - (i + 1)

carefully accounts for zero-based indexing, which ensures correct results even for minimal inputs.