Find First K Missing Positive Numbers

Explanation & Solution

Description

Given an unsorted array of integers nums and a positive integer k, return the first `k` missing positive integers that are not present in nums.

The result should be returned in ascending order.

Input:nums = [3, -1, 4, 5, 5], k = 3

-1

Output:[1, 2, 6]

Explanation: Missing positives in order: 1, 2, 6, 7... The first 3 are [1, 2, 6].

Constraints

1 <= nums.length <= 10^4
-10^5 <= nums[i] <= 10^5
1 <= k <= 50

Approach

Cyclic Sort pattern

1. Phase 1 — Cyclic Sort (Ignore Out-of-Range Values)

For each index i, only place nums[i] at index nums[i] - 1 if:
nums[i] > 0 (positive)
nums[i] <= n (within array bounds)
nums[i] !== nums[j] (not a duplicate already in place)
Skip negatives, zeros, values > n, and duplicates

2. Phase 2 — Collect Missing from [1..n]

After sorting, scan indices 0 to n-1
If nums[x] !== x + 1, then x + 1 is missing — add it to the result
Stop as soon as k missing numbers are found

3. Extend Beyond n if Needed

If fewer than k missing numbers were found in range [1, n], continue with n+1, n+2, ...
Track values > n that were in the original array (via a Set) to skip them correctly

🧠 Key Insight

This extends the classic cyclic sort pattern to handle arbitrary values and multiple missing numbers in a single unified approach

Time

O(n + k)linear sort pass plus at most n + k iterations

Space

O(n) for the extra-nums set in the worst case

Visualization

Input:

[3, -1, 4, 5, 5], k = 3

—

Press ▶ or use ← → to step through

Pointer iPointer jProcessedDone

13 steps

Solution Code

Kth Missing Positive Number

Minimum Swaps to Sort