Cyclic Sort
Every value has a home index. Keep swapping values into place; whatever is out of place afterwards is the answer.
ArraysO(n) time, O(1) spaceNew7 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
numbers in range 1..n
missing number
duplicate number
first missing positive
The template
Get this into muscle memory, then adapt the condition per problem.
let i = 0;
while (i < n) {
const j = nums[i] - 1;
if (nums[i] !== nums[j]) [nums[i], nums[j]] = [nums[j], nums[i]];
else i++;
} Watch Cyclic SortIf you are stuck
The generic hint ladder for this pattern, in order.
- 1Values are bounded by n, which is a strong hint about index mapping.
- 2Value v belongs at index v-1.
- 3Each swap places at least one value correctly, so the loop is linear.
Drill it
Every problem in the bank that uses this pattern.
0 / 7 solved