Find the First K Missing Positive Numbers
Mahabharata — The K Absent Warriors — The First K Ranks Left Unfilled
प्रथमाः क लुप्ताः धनात्मकाः — तेषां नामानि सूचय। क्रमेण अनुपस्थितान् ज्ञात्वा — रिक्तस्थानानि पूरय॥
*The first k absent positive ones — list their names. Know the absent ones in order — fill the empty positions.*
The Story
Like cs-7 but find the FIRST K missing positive numbers, not just the first one.
For `nums = [3,4,-1,1]`, k=2: missing are [2, 5]. For `nums = [2,3,4]`, k=3: missing are [1, 5, 6].
**Step 1 — Cyclic sort** (same as cs-7): Place valid numbers (1..n) at their correct indices. Ignore invalid.
**Step 2 — Scan for in-array missing:** Traverse 0..n-1. If nums[i] ≠ i+1, then i+1 is a missing positive ≤ n. Collect these.
**Step 3 — Extend beyond n if needed:** After collecting k1 missing numbers from inside the array, if k1 < k, continue with n+1, n+2, ... until we have k total.
But careful: some numbers from nums might be > n and already account for some missing slots. We need to avoid adding those.
For `nums = [3,4,-1,1]`, n=4, k=2: Cyclic sort → [1,-1,3,4] Scan: i=1: nums[1]=-1≠2 → add 2. k_found=1. Need 1 more. Extras: n+1=5, n+2=6... But nums has no values >n that would "consume" 5+, so add 5. Result: [2, 5] ✓
For `nums = [2,3,4,7,8]`, k=3, n=5: Cyclic sort → [_,2,3,4,_] (1 missing, 5 missing) Scan: i=0: nums[0]≠1 → add 1. i=4: nums[4]≠5 → add 5. k_found=2. Need 1 more from n+1=6, n+2=7... But nums contains 7! So skip 7, try 8... nums contains 8! Try 9... → add 6. Wait — 7 and 8 are already in nums but ≥ n+1. We need to track which of those are in nums.
Handle with a set of values from nums that are > n: Set extraLarge = {7, 8}. Then for extending: try n+1=6 (not in extraLarge) → add 6. k_found=3. Return [1, 5, 6].
This complete approach handles all edge cases.
The Sequential Counter
Use a HashSet of all nums. Try 1, 2, 3, ... collect first k not in set. O(n+k) time, O(n) space.
public List<Integer> findFirstKMissingPositiveBruteForce(int[] nums, int k) {
Set<Integer> set = new HashSet<>();
for (int x : nums) set.add(x);
List<Integer> result = new ArrayList<>();
for (int i = 1; result.size() < k; i++)
if (!set.contains(i)) result.add(i);
return result;
}The Cyclic Sort + Extension Wisdom
public List<Integer> findFirstKMissingPositive(int[] nums, int k) {
int n = nums.length;
// Cyclic sort
int i = 0;
while (i < n) {
int correct = nums[i] - 1;
if (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[correct]) {
int temp = nums[i]; nums[i] = nums[correct]; nums[correct] = temp;
} else i++;
}
// Collect missing within array
List<Integer> result = new ArrayList<>();
Set<Integer> extraLarge = new HashSet<>();
for (int j = 0; j < n && result.size() < k; j++) {
if (nums[j] != j + 1) {
result.add(j + 1);
extraLarge.add(nums[j]);
}
}
// Extend beyond n if needed
int extra = n + 1;
while (result.size() < k) {
if (!extraLarge.contains(extra)) result.add(extra);
extra++;
}
return result;
}Step-by-Step Walkthrough
nums=[2,3,4], k=3
Cyclic sort: 2→idx1, 3→idx2, 4→idx3? n=3, so 4>n, skip.
Array: [_,2,3] where _=4 (4 is out of range, stays in place)
Actually: nums=[2,3,4], n=3.
i=0: nums[0]=2,correct=1. swap→[3,2,4]. i stays 0
i=0: nums[0]=3,correct=2. swap→[4,2,3]. i stays 0
i=0: nums[0]=4>n. skip→i++
i=1: 2→correct=1. match→i++
i=2: 3→correct=2. match→i++
Array: [4,2,3]
Scan: i=0: nums[0]=4≠1 → add 1, extraLarge={4}
i=1,i=2: match.
k_found=1. Need 2 more.
Extend: 4: in extraLarge → skip. 5: not in extraLarge → add. 6 → add.
Return [1,5,6] ✅Deep Insight
**Why track extraLarge?** Numbers from nums that are >n take up indices in the extension range. E.g., if nums has 7 and we're looking for missing positives >5, we must skip 7 (it's present in nums).
**cs-7 vs cs-8:** - cs-7: return first index j+1 after cyclic sort. Single answer. - cs-8: collect up to k missing numbers, extending beyond n if needed.
**extraLarge set size:** At most n elements (nums has n elements), so space is O(min(k,n)).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n+k) | O(n) | HashSet for all values |
| Optimal | O(n+k) | O(k) | Cyclic sort + extraLarge set (at most k elements) |
Pattern Recognition
✅ Find first k missing positive numbers ✅ Cyclic sort + scan within array + extend beyond n ✅ Track extraLarge set for values >n in nums ✅ Extension loop skips numbers already in nums **LeetCode Trigger Phrases:** → "first k missing positive numbers" → "k smallest missing positives" → Extension of cs-7 for multiple missing
Bhagavad Gita 4.5
बहूनि मे व्यतीतानि जन्मानि तव चार्जुन। तान्यहं वेद सर्वाणि न त्वं वेत्थ परन्तप॥
Many births of Mine have passed away, and also of yours, O Arjuna. I know them all, but you do not, O Scorcher of Foes.
Connection: Krishna knows all the missing — those who have passed, those who have yet to come — just as the algorithm knows all k missing positives, even those beyond the array's horizon (beyond n). The set of 'extraLarge' is like divine memory of who is already present in the cosmic register, ensuring no already-present soul is mistakenly listed as absent. The algorithm extends its search systematically into the infinite, collecting the first k vacancies in the order of dharmic priority.