06
Cyclic Sort
Problems over a fixed 1..N range.
4 pages
- Pattern 06: Cyclic SortPattern guide
The trigger is narrow but unmistakable: n numbers drawn from the range 1..n (or 0..n-1), and the interviewer wants O(1) extra space. The array itself…
- LC 448Find All Numbers Disappeared in an Array (LC 448)Easy
Values live in [1, n] and indices are 0..n-1, so each value has a “home” index value - 1; either swap everyone home (cyclic sort) or mark visited homes…
- LC 136Single Number (LC 136)Easy
XOR is commutative and associative, and a ^ a = 0, a ^ 0 = a, so pairing duplicates cancels them and leaves the singleton.
- LC 645Set Mismatch (LC 645)Easy
Numbers should be 1..n at indices 0..n-1; after placing each x at index x-1, the first slot where nums[i] != i+1 reveals the duplicate (the value stuck…