Definition
- Cyclic placement – identical to smallest-missing-positive: each in-range value v is placed at index v-1.
- Index scan – walk indices 0 to n-1; when the slot value is wrong, that index+1 is missing and the stray value in the slot is recorded.
- Extension past n – if fewer than k missing numbers are found, continue counting from n+1 upward, skipping any numbers that appeared as strays.
- Stray set – records values greater than n (or duplicates) that were displaced during placement and must not be emitted during extension.
- Bounded space – the stray set grows at most O(k) because the collection stops once k results are found.
The National Bank of India needs the next k free account suffix numbers for a corporate onboarding batch. The clerk files all currently-used suffixes into their slots, lists every empty slot as a free suffix, and if still short of k, keeps counting upward past n while skipping suffixes already in use.
Understanding the Concepts
What is the First K Missing Positive Numbers problem?
Given an unsorted array with duplicates, negatives, and zeros, return the first k positive integers that do not appear in the array, in ascending order. This extends the single-missing-positive problem to finding multiple missing numbers. The target is O(n + k) time and O(k) extra space.
package com.bank.onboarding;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class FirstKMissing {
public static List<Integer> findFirstKMissing(int[] suffixes, int k) {
int n = suffixes.length;
// Phase 1: Cyclic placement
for (int i = 0; i < n; i++) {
while (suffixes[i] > 0 && suffixes[i] <= n
&& suffixes[i] != suffixes[suffixes[i] - 1]) {
int target = suffixes[i] - 1;
int temp = suffixes[i];
suffixes[i] = suffixes[target];
suffixes[target] = temp;
}
}
List<Integer> result = new ArrayList<>();
Set<Integer> strays = new HashSet<>();
// Phase 2: Scan indices for empty homes
for (int i = 0; i < n && result.size() < k; i++) {
if (suffixes[i] != i + 1) {
result.add(i + 1); // i+1 is missing
strays.add(suffixes[i]); // record the stray
}
}
// Phase 3: Extend past n
int candidate = n + 1;
while (result.size() < k) {
if (!strays.contains(candidate)) {
result.add(candidate);
}
candidate++;
}
return result;
}
}
Why does cyclic placement work the same as the single-missing version?
The placement phase is identical to the smallest-missing-positive problem. Each value v in range 1 to n is sent to index v-1. Negatives, zeros, values greater than n, and duplicates already at their home are skipped. After placement, every in-range value that exists in the array sits at its correct home index.
package com.bank.onboarding;
public class PlacementDemo {
public static void trace() {
int[] suffixes = {2, 3, 4};
int n = 3;
// After cyclic placement:
// 2 -> index 1, 3 -> index 2, 4 -> out of range
// Result: [4, 2, 3] (4 is a stray at index 0)
// Index 0 holds 4 != 1, so 1 is missing
// Stray: {4}
System.out.println("After placement: value 1 is missing at index 0");
}
}
How does the index scan phase work?
Walk indices 0 to n-1. When suffixes[i] != i + 1, the value i + 1 is missing from the array, so add it to the result. The value actually sitting in that slot is a stray: it is a number greater than n or a duplicate that got displaced. Record it in a set because it represents a number that exists in the array and must not be emitted later during the extension phase.
package com.bank.onboarding;
public class ScanDemo {
public static void trace() {
int[] suffixes = {4, 2, 3}; // after placement of [2, 3, 4]
int n = 3;
// Index 0: suffixes[0]=4 != 1 → 1 is missing, stray={4}
// Index 1: suffixes[1]=2 == 2 → correct
// Index 2: suffixes[2]=3 == 3 → correct
// Missing so far: [1]
// If k=3, need 2 more from extension phase
}
}
How does the extension phase work?
If the index scan yields fewer than k missing numbers, continue counting upward from n+1. For each candidate, check whether it exists in the stray set. If it does, skip it because it is a number that was present in the original array. If it does not, add it to the result. Stop when the result has k entries.
package com.bank.onboarding;
import java.util.HashSet;
import java.util.Set;
public class ExtensionDemo {
public static void trace() {
// After scan: missing = [1], strays = {4}
int n = 3;
int k = 3;
Set<Integer> strays = new HashSet<>();
strays.add(4);
// candidate = 4: in strays, skip
// candidate = 5: not in strays, emit → missing = [1, 5]
// candidate = 6: not in strays, emit → missing = [1, 5, 6]
// Done: result = [1, 5, 6]
System.out.println("Result: [1, 5, 6]");
}
}
Why is the stray set bounded by O(k)?
The stray set only grows during the index scan, and only when a slot is wrong (meaning a missing number is found). Since we stop the scan as soon as the result reaches k entries, we add at most k strays. The extension phase only reads from the set, never adds to it. So the set size is at most k, keeping the extra space at O(k) rather than O(n).
// Space analysis:
// - result list: at most k entries
// - stray set: at most k entries (one per missing found in scan)
// - Total extra space: O(k)
// - The array itself is modified in-place (O(1) extra for placement)
What are edge cases?
Edge cases include an empty array (first k positives are 1, 2, ..., k), an array with a perfect 1-to-n sequence (missing are n+1, n+2, ..., n+k), and an array where all elements are the same value.
package com.bank.onboarding;
import java.util.List;
public class EdgeCases {
public static void test() {
// Empty array, k=3: result = [1, 2, 3]
System.out.println(FirstKMissing.findFirstKMissing(new int[]{}, 3));
// Perfect: [1,2,3], k=2: result = [4, 5]
System.out.println(FirstKMissing.findFirstKMissing(new int[]{1, 2, 3}, 2));
// All same: [5,5,5], k=3: result = [1, 2, 3]
System.out.println(FirstKMissing.findFirstKMissing(new int[]{5, 5, 5}, 3));
}
}
[1, 2, 3]
[4, 5]
[1, 2, 3]
What is the time and space complexity?
| Phase | Time | Space |
|---|---|---|
| Cyclic placement | O(n) | O(1) in-place |
| Index scan | O(n) | O(k) for strays |
| Extension | O(k) amortized | O(k) for result |
| Total | O(n + k) | O(k) |
What are common mistakes?
The most common mistake is forgetting to record strays during the index scan, which causes the extension phase to emit numbers that actually exist in the array. Another mistake is not stopping the scan early when the result already has k entries, which wastes time and inflates the stray set unnecessarily.
package com.bank.onboarding;
public class CommonMistakes {
// WRONG: not recording strays
public static void wrongVersion(int[] suffixes, int k) {
// After placement, scan for missing:
// Index 0 has stray value 4, emit 1 as missing
// Extension: candidate 4, NOT in strays (forgot to record!)
// Emits 4 as missing, but 4 exists in the array!
// Fix: record suffixes[i] in stray set when slot is wrong
}
// WRONG: not stopping scan early
public static void wrongScanAll(int[] suffixes, int k) {
// Scans all n indices even when result already has k entries
// Wastes time and inflates stray set
// Fix: add "result.size() < k" to scan loop condition
}
}
How is this used in a banking context?
At the National Bank of India, the onboarding team needs exactly k of the smallest unused positive account suffix numbers for a corporate batch opening. The suffix pool is an in-memory array of already-assigned suffixes mixed with duplicates and negative placeholders. Filing the valid suffixes home, listing the empty homes, and then extending past n while skipping observed strays produces the k free suffixes efficiently.
package com.bank.onboarding;
import java.util.List;
public class AccountSuffixAllocator {
public static void main(String[] args) {
int[] assignedSuffixes = {3, -1, 4, 1, 3, 7};
int k = 4;
List<Integer> freeSuffixes = FirstKMissing.findFirstKMissing(assignedSuffixes, k);
System.out.println("Next " + k + " free suffixes: " + freeSuffixes);
}
}
Next 4 free suffixes: [2, 5, 6, 8]
Visual Overview
Three-Phase Algorithm
======================
Input: [2, 3, 4], k=3
Phase 1: Cyclic Placement
─────────────────────────
[2, 3, 4]
↓ place 2 at index 1
[3, 2, 4]
↓ place 3 at index 2
[4, 2, 3]
↓ 4 > n=3, stop
Result: [4, 2, 3]
Phase 2: Index Scan
───────────────────
Index 0: 4 != 1 → emit 1, record stray {4}
Index 1: 2 == 2 → skip
Index 2: 3 == 3 → skip
Missing so far: [1]
Strays: {4}
Phase 3: Extension past n=3
───────────────────────────
candidate=4: in strays → skip
candidate=5: not in strays → emit [1, 5]
candidate=6: not in strays → emit [1, 5, 6]
Done! result.size() == k == 3
Final result: [1, 5, 6]
Stray Set Bounding
==================
┌─────────────────────────────────────┐
│ Index scan emits at most k missing │
│ Each emit records one stray │
│ Stray set size <= k │
│ Extension only reads, never adds │
└─────────────────────────────────────┘
Key Takeaway
Finding the first k missing positive numbers extends the single-missing-positive technique from one answer to k answers, and the algorithm has three clean phases. First you run cyclic placement to send each in-range positive value to its home index, skipping negatives, zeros, and values larger than n. Then you scan the indices and emit index plus one for every slot whose stored value is wrong, recording the stray value in that slot because it represents a number that exists in the array.
If the index scan does not yield k missing numbers, you continue counting upward from n+1 and emit each candidate that is not in the stray set. The stray set stays small because it grows by at most one per missing number found during the scan, and you stop as soon as the result has k entries. This keeps the extra space at O(k) rather than O(n), and the total time is O(n + k).
At the National Bank of India, the onboarding team used this to pre-allocate blocks of free account suffix numbers during corporate batch openings. The suffix pool was an in-memory array of already-assigned suffixes mixed with duplicates and negative placeholders, and the team needed exactly k of the smallest unused positive suffixes in ascending order. Filing the valid suffixes home, listing the empty homes, and extending past n while skipping observed strays produced the answer efficiently.
The critical detail is recording strays during the index scan. Without the stray set, the extension phase would emit numbers that actually exist in the array, producing incorrect results.
Remember one sentence: cyclic-place, emit empty homes, then extend past n skipping strays until you have k missing positives.
---