Recognition Cheat Sheet
| If you see… | Think… |
|---|---|
Numbers from 1 to n | Cyclic Sort |
| Numbers map directly to indices | Cyclic Sort |
| Find missing number | Cyclic Sort |
| Find duplicate number | Cyclic Sort |
| Find all missing numbers | Cyclic Sort |
| Find all duplicates | Cyclic Sort |
Main Trigger
Numbers in a fixed range → Value tells you the correct index → Cyclic Sort
The Basic Idea
If the array contains numbers from 1 to n, each number has a correct index:
1 → index 0
2 → index 1
3 → index 2
...
n → index n - 1So keep swapping each number into its correct position.
[3, 1, 5, 4, 2]
3 → index 2
[5, 1, 3, 4, 2]
5 → index 4
[2, 1, 3, 4, 5]
2 → index 1
[1, 2, 3, 4, 5]1. Cyclic Sort
Watch value 3 chain-swap its way home — every swap lands one number in its final slot.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Cyclic Sort
You are given an array of distinct integers from 1 to n in random order. Sort the array in place by repeatedly swapping each value directly to its correct index. A value v belongs at index v−1. For example, in [3, 1, 5, 4, 2], the value 3 belongs at index 2, so swap it there.
Value v belongs at index v−1. At each position, if the value isn't home, swap it to its correct slot and stay put (the incoming value may also be misplaced). Advance only when the current index is correct. At most n swaps → O(n).
1
i = 0
2
while i < n:
3
correct = nums[i] - 1 // value v lives at index v−1
4
if nums[i] != nums[correct]:
5
swap(nums, i, correct) // send it home, stay at i
6
else:
7
i++ // already home, move on
public void cyclicSort(int[] nums) {
int i = 0;
while (i < nums.length) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct]) {
swap(nums, i, correct);
} else {
i++;
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}def cyclic_sort(nums):
i = 0
while i < len(nums):
correct = nums[i] - 1
if nums[i] != nums[correct]:
nums[i], nums[correct] = nums[correct], nums[i]
else:
i += 1void cyclicSort(vector<int>& nums) {
int i = 0;
while (i < (int)nums.size()) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct]) {
swap(nums[i], nums[correct]);
} else {
i++;
}
}
}function cyclicSort(nums) {
let i = 0;
while (i < nums.length) {
const correct = nums[i] - 1;
if (nums[i] !== nums[correct]) {
[nums[i], nums[correct]] = [nums[correct], nums[i]];
} else {
i++;
}
}
}Key Idea
correct index of value v = v - 1 // for range 1..nValue tells you where it belongs.
Complexity
Time: O(n)
Space: O(1)2. Find Missing Number
The out-of-range value 3 can never be placed — the gap it leaves behind is the answer.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Missing Number
You are given an array of length n containing integers from 0 to n, inclusive, with exactly one number missing. Find that missing number. For example, in [3, 0, 1], the number 2 is absent.
Cyclic‑sort each in‑range value to its index; a value equal to n has no slot and is skipped. After one pass, the first index where nums[i] ≠ i is the missing number.
1
i = 0
2
while i < n:
3
correct = nums[i] // 0‑based: v belongs at index v
4
if nums[i] < n && nums[correct] != nums[i]:
5
swap(nums, i, correct)
6
else:
7
i++ // n itself has no slot — skip it
8
scan: first i with nums[i] != i is the missing number
Numbers are from 0 to n, with one number missing.
Example:
[3, 0, 1]
Expected:
[0, 1, 2, 3]
Missing = 2public int missingNumber(int[] nums) {
int i = 0;
while (i < nums.length) {
int correct = nums[i];
if (nums[i] < nums.length &&
nums[i] != nums[correct]) {
swap(nums, i, correct);
} else {
i++;
}
}
for (i = 0; i < nums.length; i++) {
if (nums[i] != i)
return i;
}
return nums.length;
}def missing_number(nums):
i = 0
while i < len(nums):
correct = nums[i]
if nums[i] < len(nums) and nums[i] != nums[correct]:
nums[i], nums[correct] = nums[correct], nums[i]
else:
i += 1
for i in range(len(nums)):
if nums[i] != i:
return i
return len(nums)int missingNumber(vector<int>& nums) {
int i = 0;
while (i < (int)nums.size()) {
int correct = nums[i];
if (nums[i] < (int)nums.size() && nums[i] != nums[correct])
swap(nums[i], nums[correct]);
else
i++;
}
for (i = 0; i < (int)nums.size(); i++)
if (nums[i] != i) return i;
return nums.size();
}function missingNumber(nums) {
let i = 0;
while (i < nums.length) {
const correct = nums[i];
if (nums[i] < nums.length && nums[i] !== nums[correct]) {
[nums[i], nums[correct]] = [nums[correct], nums[i]];
} else {
i++;
}
}
for (let j = 0; j < nums.length; j++) {
if (nums[j] !== j) return j;
}
return nums.length;
}Recognition
Numbers
0..n+ one missing → Cyclic Sort
3. Find Duplicate Number
Two copies of 2 fight over index 1 — the loser ends up parked at the wrong index.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Find The Duplicate Number
You are given an array of n+1 integers where every value is between 1 and n. By the pigeonhole principle, at least one value must appear more than once. Find the repeated value without using extra space. For example, in [1, 3, 4, 2, 2], the value 2 appears twice — the extra copy has nowhere to sit.
Cyclic-sort until a value meets its own copy already sitting at its home index — that collision means two numbers want the same slot, so the arriving value is the duplicate. Equivalent to cycle detection via array indices.
1
i = 0
2
while i < n:
3
correct = nums[i] - 1
4
if nums[i] != nums[correct]:
5
swap(nums, i, correct)
6
else:
7
i++ // stuck ⇒ two copies want this slot
8
scan: first i with nums[i] != i → duplicate = nums[i]
If two numbers want the same position, one is a duplicate.
Example:
[1, 3, 4, 2, 2]
2 → index 1
Another 2 → index 1
Duplicate = 2public int findDuplicate(int[] nums) {
int i = 0;
while (i < nums.length) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct]) {
swap(nums, i, correct);
} else {
if (i != correct)
return nums[i];
i++;
}
}
return -1;
}def find_duplicate(nums):
i = 0
while i < len(nums):
correct = nums[i] - 1
if nums[i] != nums[correct]:
nums[i], nums[correct] = nums[correct], nums[i]
else:
if i != correct:
return nums[i]
i += 1
return -1int findDuplicate(vector<int>& nums) {
int i = 0;
while (i < (int)nums.size()) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct]) {
swap(nums[i], nums[correct]);
} else {
if (i != correct) return nums[i];
i++;
}
}
return -1;
}function findDuplicate(nums) {
let i = 0;
while (i < nums.length) {
const correct = nums[i] - 1;
if (nums[i] !== nums[correct]) {
[nums[i], nums[correct]] = [nums[correct], nums[i]];
} else {
if (i !== correct) return nums[i];
i++;
}
}
return -1;
}Recognition
Numbers
1..n+ duplicate → Cyclic Sort
4. Find All Missing Numbers
After sorting, indices 4 and 5 still hold strangers — 5 and 6 never arrived.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Find All Missing Numbers
You are given an array of length n where every value is between 1 and n. Some values appear twice, which means some numbers from 1..n are missing entirely. Return every number that is absent. For example, in [4, 3, 2, 7, 8, 2, 3, 1], the values 5 and 6 never appear — the duplicates 2 and 3 are squatting on their slots.
Cyclic-sort the values to their 1-based indices (skipping when a duplicate blocks the slot). Then any index i holding a value other than i+1 marks the missing number i+1.
1
i = 0
2
while i < n:
3
correct = nums[i] - 1
4
if nums[i] != nums[correct]:
5
swap(nums, i, correct)
6
else:
7
i++
8
scan: at each i, expected value is i+1 — any mismatch marks a missing number
Numbers are from 1 to n, but some numbers are missing.
Example:
[4, 3, 2, 7, 8, 2, 3, 1]
After Cyclic Sort:
[1, 2, 3, 4, 3, 2, 7, 8]
Indices where value doesn't match:
5 → missing 5
6 → missing 6public List<Integer> findDisappearedNumbers(int[] nums) {
int i = 0;
while (i < nums.length) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct]) {
swap(nums, i, correct);
} else {
i++;
}
}
List<Integer> result = new ArrayList<>();
for (i = 0; i < nums.length; i++) {
if (nums[i] != i + 1)
result.add(i + 1);
}
return result;
}def find_disappeared_numbers(nums):
i = 0
while i < len(nums):
correct = nums[i] - 1
if nums[i] != nums[correct]:
nums[i], nums[correct] = nums[correct], nums[i]
else:
i += 1
return [i + 1 for i in range(len(nums)) if nums[i] != i + 1]vector<int> findDisappearedNumbers(vector<int>& nums) {
int i = 0;
while (i < (int)nums.size()) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct])
swap(nums[i], nums[correct]);
else
i++;
}
vector<int> result;
for (i = 0; i < (int)nums.size(); i++)
if (nums[i] != i + 1) result.push_back(i + 1);
return result;
}function findDisappearedNumbers(nums) {
let i = 0;
while (i < nums.length) {
const correct = nums[i] - 1;
if (nums[i] !== nums[correct]) {
[nums[i], nums[correct]] = [nums[correct], nums[i]];
} else {
i++;
}
}
const result = [];
for (let j = 0; j < nums.length; j++)
if (nums[j] !== j + 1) result.push(j + 1);
return result;
}Recognition
Find all missing values from
1..n→ Cyclic Sort
5. Find All Duplicates
A value meeting its own twin at the twin’s home index is caught red-handed.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Find All Duplicates
You are given an array of length n where every value is between 1 and n. Some values appear twice while others are missing entirely. Return every value that appears twice. For example, in [2, 3, 4, 3, 2], the values 3 and 2 each appear twice — sorting each value toward its home slot flushes both twins out.
Run cyclic sort; whenever the current value equals the value already at its home index (but i ≠ correct), a twin is detected — record it and move on. Each duplicate is caught the moment it meets its copy.
1
dups = []
2
while i < n:
3
correct = nums[i] - 1
4
if nums[i] != nums[correct]:
5
swap(nums, i, correct)
6
else:
7
if i != correct: dups.add(nums[i]) // twin detected
8
i++
After placing numbers in their correct positions, duplicates are the values that appear where another value should be.
public List<Integer> findDuplicates(int[] nums) {
int i = 0;
while (i < nums.length) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct]) {
swap(nums, i, correct);
} else {
i++;
}
}
List<Integer> result = new ArrayList<>();
for (i = 0; i < nums.length; i++) {
if (nums[i] != i + 1)
result.add(nums[i]);
}
return result;
}def find_duplicates(nums):
i = 0
while i < len(nums):
correct = nums[i] - 1
if nums[i] != nums[correct]:
nums[i], nums[correct] = nums[correct], nums[i]
else:
i += 1
return [nums[i] for i in range(len(nums)) if nums[i] != i + 1]vector<int> findDuplicates(vector<int>& nums) {
int i = 0;
while (i < (int)nums.size()) {
int correct = nums[i] - 1;
if (nums[i] != nums[correct])
swap(nums[i], nums[correct]);
else
i++;
}
vector<int> result;
for (i = 0; i < (int)nums.size(); i++)
if (nums[i] != i + 1) result.push_back(nums[i]);
return result;
}function findDuplicates(nums) {
let i = 0;
while (i < nums.length) {
const correct = nums[i] - 1;
if (nums[i] !== nums[correct]) {
[nums[i], nums[correct]] = [nums[correct], nums[i]];
} else {
i++;
}
}
const result = [];
for (let j = 0; j < nums.length; j++)
if (nums[j] !== j + 1) result.push(nums[j]);
return result;
}Recognition
Find all duplicates in
1..n→ Cyclic Sort
The Pattern Behind All of Them
Most Cyclic Sort problems follow the same two steps:
1. Put every number in its correct position
↓
2. Scan for positions that are incorrectFor example:
Missing number
→ Incorrect index tells you what is missing
Duplicate number
→ Correct position already occupied
All missing numbers
→ Collect incorrect indices
All duplicates
→ Collect incorrect valuesCommon Mistakes
1. Wrong index
For numbers 1..n:
correct = nums[i] - 1For numbers 0..n:
correct = nums[i]2. Incrementing after a swap
Don’t do this:
swap(nums, i, correct)
i += 1 ← WRONGAfter the swap, the new value at i may still be in the wrong position.
Wrong value
↓
Swap
↓
Check same index again3. Infinite loop with duplicates
Before swapping, make sure the target position does not already contain the same value:
if nums[i] != nums[correct]:
swap(nums, i, correct)
else:
i += 1Pattern Summary
Numbers 1..n
↓
Value → Correct Index
↓
Swap into place
↓
Scan incorrect positionsMissing number
→ Find incorrect index
Duplicate
→ Target position already occupied
All missing
→ Collect incorrect indices
All duplicates
→ Collect incorrect valuesInterview Rule
If the values belong to a fixed range and each value maps directly to an array index, think Cyclic Sort.
Quick Rule
Value → Index → Swap → Scan
Premium Content
Unlock Cyclic Sort and all premium lessons with a subscription.
From ₹199.99/year — See plans