Cyclic Sort — How the Pattern Works
Cyclic Sort is an in-place array indexing pattern for inputs whose elements come from a known bounded integer range such as [1, n] or [0, n]. Rather than comparing arbitrary element pairs, it maps each in-range value v directly to its deterministic target index (such as j = v - 1 or j = v) and swaps misplaced values into their home slots. Maintaining the invariant that every swap permanently places at least one element into its final index bounds total swaps to at most n, reducing O(n log n) comparison sorting or O(n) hash-set space to O(n) time and O(1) auxiliary space.
- The input is a mutable integer array of length n whose values are drawn from a contiguous [1, n] or [0, n] domain, possibly with missing, duplicate, or out-of-bounds entries.
- The problem asks for missing numbers, duplicate values, corrupt pairs, or the smallest missing positive integer under strict O(n) time and O(1) auxiliary space constraints.
- Each valid element v has a deterministic home index (j = v - 1 for 1-indexed ranges or j = v for 0-indexed ranges), enabling the input array itself to act as a direct-address presence table.
- Elements belong to fixed index classes (such as even values at even indices and odd values at odd indices) where paired misfits can be resolved in-place via swaps.
- Checking i != j instead of nums[i] != nums[j] before swapping: when duplicate values exist, comparing indices causes an infinite loop as two identical numbers swap endlessly.
- Advancing pointer i unconditionally inside a for-loop after a swap: incrementing i immediately skips placing the newly swapped-in element now sitting at nums[i].
- Confusing 0-indexed and 1-indexed target mappings or omitting bounds guards: [0, n] maps v to index v (skipping v == n), whereas [1, n] maps v to v - 1 and must check 0 <= j < n when arbitrary integers are allowed.
- Omitting the post-scan fallback return: if every index i in 0..n - 1 already holds its expected value, the missing integer lies just past the array bounds (n for [0, n] or n + 1 for [1, n]).
def cyclic_sort_1_to_n(nums: list[int]) -> list[int]:
i = 0
while i < len(nums):
j = nums[i] - 1
if nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i]
else:
i += 1
return numsdef first_missing_in_range(nums: list[int]) -> int:
n, i = len(nums), 0
while i < n:
j = nums[i] - 1
if 0 <= j < n and nums[i] != nums[j]:
nums[i], nums[j] = nums[j], nums[i]
else:
i += 1
for i, v in enumerate(nums):
if v != i + 1:
return i + 1
return n + 1