09. Cyclic Sort

TL;DR

When values are integers in a known range (classically 1 through n for length n) and duplicates/missing slots obey that structure, you can place each value at index value - 1 by swapping in O(n) time and O(1) extra space. After the array settles, indices that still mismatch reveal missing or duplicate values; scanning again collects all duplicates or disappeared numbers when the index rules extend to ≤ n.

Core Basics

Object: permute values so each value v tries to sit at index v−1 for 1..n problems; detects missing/duplicate cycles.
Precondition: values map to indices; breaks if domain is not [1..n] bijection without translation.
Staff-level bar: explain in-place permutation cycles vs hash set trade-off.

Recognition Cues

Phrases: “find missing number,” “find duplicate,” “first missing positive,” “all numbers disappeared,” “each appears twice except,” constraints 1..n or permutations with one anomaly.
Inputs: []int length n, values bounded so index mapping is valid or can be normalized (after ignoring out-of-range).
Outputs: single int, list of missing/duplicate, or sorted permutation side effect.

Use-case Lens

Best when: values are supposed to map directly to indices, usually 1..n or 0..n-1, and you need missing/duplicate numbers in-place.
Not for: arbitrary values without bounded index mapping.
Main invariant: if a value belongs in the array, keep swapping it toward its home index until the current index is correct or blocked by a duplicate.
Interview move: state the mapping out loud: value v belongs at index v-1 or v.

Diagram

Loading diagram…

Step-by-step Visual

Example: Sort numbers 1..5 in [3, 1, 5, 4, 2]. Each value v belongs at index v - 1.

Loading diagram…

Understanding

Each swap moves at least one element toward its home; each index is fixed at most a constant number of times before the walker advances — hence linear time. The invariant: after completion, for every valid slot index, either nums[index] == index + 1 or the slot holds an unplaceable value (duplicate or out of range) that you skip.

Generic Recipe

Walk index from 0 to n-1.
Let value = nums[index]. While value is in [1, n] and nums[value-1] != value, swap nums[index] with nums[value-1] (put value home).
Second pass: mismatch nums[index] != index + 1 exposes missing (index + 1) or duplicate (what landed wrong).
For all duplicates: collect indices where nums[index] != index + 1 after sorting phase; values at those positions are duplicates when the multiset allows it.
First missing positive variants extend range checks (ignore ≤ 0 or > n).

Complexity

Time: O(n) — each swap places one element; pointer index advances only when home or stuck.
Space: O(1) extra (mutate input array).

Memory Hooks

Operational mantra: if value v belongs at index v-1, swap until each position is correct or proven impossible.
Anti-panic: if values map to indices, ask whether mutation is allowed; if not, cyclic placement may be disqualified.

Study Pattern (SDE3+)

Recognition drill (10 min): spot [1..n], missing/duplicate, and "O(1) extra space" placement cues.
Implementation sprint (25 min): code first missing positive or missing number with guarded swaps and duplicate checks.
Staff follow-up (10 min): explain read-only alternatives, out-of-range values, and why each swap places one value correctly.

Generic Code Template

Go

package main

func cyclicSortOneToN(nums []int) {
	length := len(nums)
	for index := 0; index < length; index++ {
		for {
			value := nums[index]
			if value < 1 || value > length {
				break
			}
			targetIndex := value - 1
			if nums[targetIndex] == value {
				break
			}
			nums[index], nums[targetIndex] = nums[targetIndex], nums[index]
		}
	}
}

// Missing number for values in [0..n] (length n): index i should hold i when possible.
func missingNumberZeroToN(nums []int) int {
	length := len(nums)
	for index := 0; index < length; index++ {
		for nums[index] < length && nums[nums[index]] != nums[index] {
			targetIndex := nums[index]
			nums[index], nums[targetIndex] = nums[targetIndex], nums[index]
		}
	}
	for index := 0; index < length; index++ {
		if nums[index] != index {
			return index
		}
	}
	return length
}

func findAllDuplicates(nums []int) []int {
	cyclicSortOneToN(nums)
	var result []int
	for index := range nums {
		if nums[index] != index+1 {
			result = append(result, nums[index])
		}
	}
	return result
}

func main() {
	missingDemo := []int{3, 0, 1}
	_ = missingNumberZeroToN(missingDemo)
	dupDemo := []int{4, 3, 2, 7, 8, 2, 3, 1}
	_ = findAllDuplicates(dupDemo)
}

JavaScript

function cyclicSortOneToN(nums) {
  const length = nums.length;
  for (let index = 0; index < length; index++) {
    while (true) {
      const value = nums[index];
      if (value < 1 || value > length) break;
      const targetIndex = value - 1;
      if (nums[targetIndex] === value) break;
      [nums[index], nums[targetIndex]] = [nums[targetIndex], nums[index]];
    }
  }
}

function missingNumberZeroToN(nums) {
  const length = nums.length;
  for (let index = 0; index < length; index++) {
    while (nums[index] < length && nums[nums[index]] !== nums[index]) {
      const targetIndex = nums[index];
      [nums[index], nums[targetIndex]] = [nums[targetIndex], nums[index]];
    }
  }
  for (let index = 0; index < length; index++) {
    if (nums[index] !== index) {
      return index;
    }
  }
  return length;
}

function findAllDuplicates(nums) {
  cyclicSortOneToN(nums);
  const result = [];
  for (let index = 0; index < nums.length; index++) {
    if (nums[index] !== index + 1) {
      result.push(nums[index]);
    }
  }
  return result;
}

Variants

Missing single: one index mismatch or n+1 answer when array is a permutation of 1..n minus one.
Duplicate (one): Floyd on indices (287) or cyclic sort; pick per problem constraints (read-only, etc.).
All duplicates / disappeared: second pass collects off-home values; dedupe if problem asks unique missing set.
Values not exactly 1..n: normalize to ignore out-of-range; first missing positive uses placement only for v in [1, n].

Representative Problems

268. Missing Number — XOR/sum alternatives; cyclic sort is O(1) space
287. Find the Duplicate Number — cyclic sort when mutation allowed; Floyd alternative when read-only
75. Sort Colors — separate technique (three-way partition); trains in-place placement discipline alongside cyclic swaps

Anti-patterns

Infinite swap loops when nums[target] == value already — always break when home or duplicate blocks placement.
Applying cyclic sort when the problem is read-only or requires O(1) memory without swapping (binary search on answer or Floyd may apply instead).
Expecting sorted output for arbitrary integers — pattern needs range/index alignment.
Confusing missing vs duplicate scan — re-read whether index+1 or nums[index] is the answer.

On this page