Cyclic Sort¶
Also known as: Index-as-Value Placement
When an array holds the numbers 1 to n in some scrambled order, every value has a natural home: value v belongs at index v-1. Walk the array putting each number where it belongs, and whatever's left out of place is the answer — the missing one, the duplicate, the mismatch.
Before you start¶
- Comfortable with array indexing and swapping in your language.
What 'solved properly' looks like
Target: O(n) time, O(1) space. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You iterate through the array, and whenever the current value is not at its correct index, you swap it to where it belongs. Then you check the swapped-in value and repeat until either the correct value is in place or you find a duplicate. After one pass, every value that can be in the right place is. Any value that isn't — missing numbers, duplicates, or both — is trivially identified in a second pass.
Why it matters: It's a rare O(n)-time, O(1)-space sort that works only on a very specific input shape (numbers in a bounded range). When that shape appears — and it appears often in interview problems — it's the difference between an O(n log n) sort-and-scan solution and a linear-time constant-space one.
When to reach for it¶
Reach for it when an array contains numbers in a known bounded range (1 to n or 0 to n), and the problem asks to "find the missing number", "find all duplicates", or "find the first missing positive." The constraint pair "without extra space and in O(n) time" is a dead giveaway.
When not to use it
It only works when values map cleanly onto indices in a bounded range. Unbounded values or arbitrary repetition break the mapping — use a hash set. And note this mutates the input, which some problems forbid.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Missing Number | LeetCode | Easy | 15 mins | teaching |
| 2 | Set Mismatch | LeetCode | Easy | 15 mins | teaching |
| 3 | Find All Numbers Disappeared in an Array | LeetCode | Easy | 20 mins | consolidation |
| 4 | Find All Duplicates in an Array | LeetCode | Medium | 25 mins | consolidation |
| 5 | First Missing Positive | LeetCode | Hard | 40 mins | challenge |
Already know this? Test out.
If you can solve First Missing Positive cleanly in one sitting — handling the out-of- range values and the cyclic placement — you already own this pattern, so move on to the next one. Note this one is Hard because it stretches the pattern to its limit with negative numbers and values outside the range. If it doesn't come easily, work the set from the top.