Definition
- Cyclic Sort with duplicates – extends the basic Cyclic Sort pattern to arrays where some values appear more than once by using a duplicate-safe swap guard.
- Placement rule – value
vbelongs at indexv - 1; the swap guardnums[i] != nums[nums[i] - 1]prevents infinite loops on duplicates. - Detection – after placement, every index where
nums[i] != i + 1marks a missing number from the range 1 to n. - Dual use – the same placement loop also reveals duplicates: any value that could not be placed because its home was already occupied is a duplicate.
- Complexity – O(n) time, O(1) extra space beyond the output list.
The National Bank of India expects one signed KYC form per customer numbered 1 to n, but some customers submitted duplicates and others never submitted. The clerk files each form in its matching locker. Any locker still holding the wrong form marks a form number that nobody ever submitted.
Understanding the Concepts
What is the find-all-missing-numbers problem?
Given an unsorted array of n integers in the range 1 to n where some numbers appear more than once (and some are therefore missing), return all the numbers in 1..n that do not appear. The challenge is to do it in O(n) time and O(1) extra space.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class FindAllMissing {
public List<Integer> findDisappearedNumbers(int[] nums) {
int i = 0;
while (i < nums.length) {
int correctIndex = nums[i] - 1;
if (nums[i] != nums[correctIndex]) {
int temp = nums[correctIndex];
nums[correctIndex] = nums[i];
nums[i] = temp;
} else {
i++;
}
}
List<Integer> missing = new ArrayList<>();
for (i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) missing.add(i + 1);
}
return missing;
}
}
Why is the duplicate-safe guard important?
Without the guard, swapping a duplicate value to a home index that already holds the same value would loop forever. The guard nums[i] != nums[nums[i] - 1] compares the value at the current position with the value at the destination. If they are the same, the value is a duplicate and swapping would not change anything, so we advance the pointer.
package com.bank.service;
public class DuplicateGuardDemo {
public static void main(String[] args) {
int[] nums = {2, 2}; // n=2, missing=1, duplicate=2
int i = 0;
while (i < nums.length) {
int dest = nums[i] - 1;
if (nums[i] != nums[dest]) {
int temp = nums[dest]; nums[dest] = nums[i]; nums[i] = temp;
System.out.println("Swapped: " + java.util.Arrays.toString(nums));
} else {
System.out.println("Skip (duplicate guard): index " + i);
i++;
}
}
// Output: Skip at both indices, nums remains [2,2]
// Index 0: nums[0]=2 != 0+1=1 -> missing 1
}
}
Skip (duplicate guard): index 0
Skip (duplicate guard): index 1
How does the placement pass work step by step?
Each value is sent to its home index. When a duplicate reaches a home that already holds the correct value, the pointer advances. After the pass, correctly placed values sit at their home indices and duplicates fill the leftover slots.
package com.bank.service;
public class PlacementTraceAll {
public static void main(String[] args) {
int[] forms = {4, 3, 2, 7, 8, 2, 3, 1}; // n=8
int i = 0;
while (i < forms.length) {
int dest = forms[i] - 1;
if (forms[i] != forms[dest]) {
int temp = forms[dest]; forms[dest] = forms[i]; forms[i] = temp;
} else {
i++;
}
}
System.out.println("After placement: "
+ java.util.Arrays.toString(forms));
// [1, 2, 3, 4, 3, 2, 7, 8]
// Index 4: 3 != 5 -> missing 5
// Index 5: 2 != 6 -> missing 6
}
}
After placement: [1, 2, 3, 4, 3, 2, 7, 8]
How is this different from the negative-marking trick?
The negative-marking trick flips the sign at index abs(v) - 1 to mark a value as present. After marking, indices with positive values are missing. Both approaches are O(n) time and O(1) extra space, but they differ in how they leave the array.
| Aspect | Cyclic Sort | Negative Marking |
|---|---|---|
| Array state after | Values at home indices | Signs flipped |
| Dual use | Also finds duplicates | Also finds duplicates (via double-negative) |
| Readability | Moderate | Slightly less intuitive |
| Restoration | Array is in sorted-like state | Must restore by taking abs |
// Negative marking alternative
for (int val : nums) {
int idx = Math.abs(val) - 1;
if (nums[idx] > 0) nums[idx] = -nums[idx];
}
for (int j = 0; j < nums.length; j++) {
if (nums[j] > 0) missing.add(j + 1);
}
What are the edge cases?
Edge cases include all elements being the same (maximum missing numbers), no duplicates (no missing numbers), and a single-element array.
package com.bank.service;
public class AllMissingEdgeCases {
public static void main(String[] args) {
FindAllMissing solver = new FindAllMissing();
// All same: [1,1,1] -> missing 2,3
System.out.println(solver.findDisappearedNumbers(new int[]{1,1,1}));
// No duplicates: [1,2,3] -> missing nothing
System.out.println(solver.findDisappearedNumbers(new int[]{1,2,3}));
// Single element: [1] -> missing nothing
System.out.println(solver.findDisappearedNumbers(new int[]{1}));
}
}
[2, 3]
[]
[]
What are common mistakes?
The most common mistake is using nums[i] != i + 1 as the swap guard instead of nums[i] != nums[nums[i] - 1]. The first guard does not detect when the destination already holds the correct value from a different position, causing infinite loops.
// WRONG: swap guard based on position
while (i < n) {
if (nums[i] != i + 1) {
swap(nums, i, nums[i] - 1); // infinite loop on duplicates!
} else { i++; }
}
// CORRECT: swap guard based on destination value
while (i < n) {
int dest = nums[i] - 1;
if (nums[i] != nums[dest]) {
swap(nums, i, dest);
} else { i++; }
}
How would you apply this in a banking system?
At the National Bank of India, every customer in a KYC batch is assigned a form number in the range 1 to n. Some customers submit duplicates and others never submit. Compliance needs the complete list of never-submitted form numbers to chase those customers.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class KYCReconciliationService {
public List<Integer> findUnsubmittedForms(int[] submittedForms) {
int i = 0;
while (i < submittedForms.length) {
int dest = submittedForms[i] - 1;
if (submittedForms[i] != submittedForms[dest]) {
int temp = submittedForms[dest];
submittedForms[dest] = submittedForms[i];
submittedForms[i] = temp;
} else {
i++;
}
}
List<Integer> unsubmitted = new ArrayList<>();
for (i = 0; i < submittedForms.length; i++) {
if (submittedForms[i] != i + 1) {
unsubmitted.add(i + 1);
}
}
return unsubmitted;
}
}
What should a senior engineer know?
A senior engineer should know that Cyclic Sort is the preferred approach when the same input must answer both the missing-numbers and the duplicate-numbers question. They should also know that the in-place modification may not be acceptable in all contexts, and that the negative-marking trick is an alternative that also modifies the array but in a different way.
// Dual use: find both missing AND duplicates in one pass
List<Integer> missing = new ArrayList<>();
List<Integer> duplicates = new ArrayList<>();
for (int j = 0; j < nums.length; j++) {
if (nums[j] != j + 1) {
missing.add(j + 1); // this number never appeared
duplicates.add(nums[j]); // this value is a duplicate
}
}
What are common interview follow-up questions?
Interviewers often follow up with these questions:
- Can you find the missing numbers without modifying the array? (Use a HashSet, O(n) space.)
- Can you also return the duplicate numbers? (Same Cyclic Sort, check leftover values.)
- What if the range is 0..n instead of 1..n? (Adjust placement: v at index v, skip n.)
// Follow-up: find missing without modifying array (O(n) space)
import java.util.HashSet;
public List<Integer> findMissingWithSet(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int val : nums) set.add(val);
List<Integer> result = new ArrayList<>();
for (int i = 1; i <= nums.length; i++)
if (!set.contains(i)) result.add(i);
return result;
}
Visual Overview
Input: [4, 3, 2, 7, 8, 2, 3, 1] n=8
Placement Pass (value v goes to index v-1):
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 4 │ 3 │ 2 │ 7 │ 8 │ 2 │ 3 │ 1 │ before
└───┴───┴───┴───┴───┴───┴───┴───┘
↓ swap, place, skip duplicates ↓
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 3 │ 2 │ 7 │ 8 │ after
└───┴───┴───┴───┴───┴───┴───┴───┘
✓ ✓ ✓ ✓ ✗ ✗ ✓ ✓
Detection Scan:
Index 4: nums[4]=3 ≠ 5 → missing 5
Index 5: nums[5]=2 ≠ 6 → missing 6
Result: [5, 6]
Key Takeaway
Finding all the missing numbers from an array over the range 1 to n, where duplicates are allowed, is the duplicate-tolerant extension of Cyclic Sort. I place each value at the index equal to the value minus one, but the critical change from the basic pattern is the swap guard: I compare the values at the two positions rather than the indices, so when a duplicate tries to swap into a slot that already holds the same value, the pointer advances instead of looping forever.
After the single placement pass, every slot whose stored value does not equal its index plus one marks a number that never appeared. The algorithm runs in linear time and uses no extra space beyond the output list. I know the negative-marking trick solves the same problem, but I favor Cyclic Sort because it leaves the array in an interpretable state and the identical loop also answers the find-all-duplicates question.
Edge cases include all elements being the same (maximum missing numbers), no duplicates (empty result), and a single-element array. The common mistake is using the wrong swap guard, which causes infinite loops on duplicates.
At the National Bank of India, this powered a KYC reconciliation job. Every customer in a batch was assigned a form number, some submitted duplicates, and others never submitted. Compliance needed the complete list of never-submitted form numbers, and the batches were too large to allocate a second tracking array.
Remember one sentence: place v at index v-1 with a duplicate-safe guard, and every mismatched slot after placement reveals a missing number.
---