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.

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.

Diagram

Pattern control flow (customize nodes for this pattern). camelCase node IDs.

Mental Model

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

1. Walk index from 0 to n-1.
2. 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).
3. Second pass: mismatch nums[index] != index + 1 exposes missing (index + 1) or duplicate (what landed wrong).
4. For all duplicates: collect indices where nums[index] != index + 1 after sorting phase; values at those positions are duplicates when the multiset allows it.
5. 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).

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.