← All patterns

Cyclic Sort

Place value `v` at index `v - 1` via in-place swaps. The canonical O(n) / O(1) primitive for missing-or-duplicate problems on arrays containing the integers `[1, n]`.

6 problems 4 Easy 1 Medium 1 Hard

When the input is a permutation (or near-permutation) of `[1, n]` or `[0, n]`, place each value at its 'home' index in O(n) time with O(1) extra space. The sort itself isn't the goal — what matters is that any post-sort mismatched index reveals a missing or duplicated value in O(1) inspection.

The trick generalizes: 'find the kth missing positive', 'find all duplicates', and 'set mismatch' all collapse to a single cyclic-placement pass followed by a linear scan.

When to reach for this pattern

  • Array of length n containing integers in `[0, n]` or `[1, n]`
  • Find the missing / duplicate / corrupt pair
  • Find the first k missing positives
  • Permutation-on-array problems with O(1) space target

Canonical template 

for (int i = 0; i < n; ) {
    if (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
        swap(nums[i], nums[nums[i] - 1]);
    else
        ++i;
}
// any index i with nums[i] != i + 1 is a mismatched home — answer slot.

C++ · adapt the names and types to your problem.

Common pitfalls

  • Infinite loop if you don't guard nums[nums[i] - 1] != nums[i] for duplicates
  • Confusing 0-indexed and 1-indexed ranges — [0, n] adjusts the home formula
  • Forgetting that values outside [1, n] should not be swapped — guard the range
  • Mutating a frozen / immutable input — many variants forbid in-place changes

Related patterns

Fast and Slow Pointers Hash Maps

Problems (6)

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.