{"title":"Cyclic Sort","description":null,"content":"Cyclic Sort is a specialized in-place sorting pattern for arrays where the values are integers in a known, dense range, typically `1` to `n` or `0` to `n-1`. When the input fits that shape, Cyclic Sort sorts the array in O(n) time and O(1) extra space, beating both comparison-based sorts (O(n log n)) and counting-style approaches that need extra arrays.\n\nCyclic Sort is an interview pattern rather than a general-purpose sorting algorithm. Many problems that ask you to find missing, duplicate, or out-of-place numbers in an array of `n` integers from `1` to `n` reduce to a Cyclic Sort plus a single scan.\n\nThis chapter covers when the pattern applies, how the cycle-by-cycle placement works, the implementation, and the family of LeetCode problems that all reduce to one or two lines on top of it.\n\n---\n\n## When the Pattern Applies\n\nCyclic Sort works when every value in the array has a clear \"home\" index. Two common signatures:\n\n1. **Array contains integers from 1 to n** (with no duplicates, or with some duplicates and missing values). The home of value `v` is index `v - 1`.\n2. **Array contains integers from 0 to n - 1**. The home of value `v` is index `v`.\n\nVariants exist for arrays of length `n` containing values from `1` to `n + 1` (the missing-positive case), but they all share the same skeleton: a value belongs at a specific index that can be computed from the value itself.\n\nIf the values are arbitrary integers or floats with no relation to indices, Cyclic Sort does not apply. Use Quick Sort, Merge Sort, or another general-purpose algorithm instead.\n\n---\n\n## The Core Idea\n\nWalk the array left to right. At each index `i`:\n\n1. Compute the home index of the current value `arr[i]`. For the 1-to-n case, the home is `arr[i] - 1`.\n2. If `arr[i]` is already at home (or out of range), move on.\n3. Otherwise, swap `arr[i]` with the element at the home index. After the swap, position `i` holds a new value that might also be out of place. **Do not advance **`i`**.** Repeat until position `i` is satisfied.\n\nThe swap is O(1), and across the entire algorithm the total number of swaps is bounded by `n` because each swap places at least one element in its correct home, where it stays. Each loop iteration either performs one such swap or advances `i`, and `i` advances at most `n` times. Total work: O(n).\n\n\n```mermaid\nflowchart LR\n A[\"arr[i]
value v\"]:::cyan\n B{\"v - 1 == i?\"}:::orange\n C[\"Already at home
advance i\"]:::green\n D[\"Swap arr[i] with arr[v - 1]\"]:::teal\n E[\"Do not advance i;
re-check the new arr[i]\"]:::orange\n\n A --> B\n B -->|Yes| C\n B -->|No| D\n D --> E\n E --> A\n\n classDef cyan fill:#00ceff,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n```\n\n\n---\n\n## Walkthrough\n\n**Input:** `arr = [3, 1, 5, 4, 2]` (values 1..5, length 5, 1-indexed).\n\n\n```shell\nStart: [3, 1, 5, 4, 2]\n\ni=0: arr[0]=3, home=2. Swap arr[0] and arr[2].\n [5, 1, 3, 4, 2] (do not advance i)\n arr[0]=5, home=4. Swap arr[0] and arr[4].\n [2, 1, 3, 4, 5] (do not advance i)\n arr[0]=2, home=1. Swap arr[0] and arr[1].\n [1, 2, 3, 4, 5] (do not advance i)\n arr[0]=1, home=0. Already home. Advance.\n\ni=1: arr[1]=2, home=1. Already home. Advance.\ni=2: arr[2]=3, home=2. Already home. Advance.\ni=3: arr[3]=4, home=3. Already home. Advance.\ni=4: arr[4]=5, home=4. Already home. Advance.\n\nFinal: [1, 2, 3, 4, 5]\n```\n\n\nIndex 0 absorbed three swaps before settling. Every other index needed zero. Across the whole array, exactly four swaps happened, one fewer than `n`, which matches the worst-case bound (`n - 1` swaps to fix `n` positions).\n\n---\n\n## Implementation\n\nThe 1-to-n variant:\n\n\n```java\npublic static void cyclicSort(int[] arr) {\n int i = 0;\n while (i < arr.length) {\n int home = arr[i] - 1; // values 1..n\n if (arr[i] != arr[home]) {\n int tmp = arr[i];\n arr[i] = arr[home];\n arr[home] = tmp;\n } else {\n i++;\n }\n }\n}\n```\n\n```python\ndef cyclic_sort(arr: list[int]) -> None:\n i = 0\n while i < len(arr):\n home = arr[i] - 1 # values 1..n\n if arr[i] != arr[home]:\n arr[i], arr[home] = arr[home], arr[i]\n else:\n i += 1\n```\n\n```cpp\nvoid cyclicSort(vector& arr) {\n int i = 0;\n while (i < (int)arr.size()) {\n int home = arr[i] - 1; // values 1..n\n if (arr[i] != arr[home]) {\n swap(arr[i], arr[home]);\n } else {\n i++;\n }\n }\n}\n```\n\n```csharp\npublic static void CyclicSort(int[] arr) {\n int i = 0;\n while (i < arr.Length) {\n int home = arr[i] - 1; // values 1..n\n if (arr[i] != arr[home]) {\n (arr[i], arr[home]) = (arr[home], arr[i]);\n } else {\n i++;\n }\n }\n}\n```\n\n```go\nfunc cyclicSort(arr []int) {\n i := 0\n for i < len(arr) {\n home := arr[i] - 1 // values 1..n\n if arr[i] != arr[home] {\n arr[i], arr[home] = arr[home], arr[i]\n } else {\n i++\n }\n }\n}\n```\n\n```rust\npub fn cyclic_sort(arr: &mut [i32]) {\n let mut i = 0usize;\n while i < arr.len() {\n let home = (arr[i] - 1) as usize; // values 1..n\n if arr[i] != arr[home] {\n arr.swap(i, home);\n } else {\n i += 1;\n }\n }\n}\n```\n\n```javascript\nfunction cyclicSort(arr) {\n let i = 0;\n while (i < arr.length) {\n const home = arr[i] - 1; // values 1..n\n if (arr[i] !== arr[home]) {\n [arr[i], arr[home]] = [arr[home], arr[i]];\n } else {\n i++;\n }\n }\n}\n```\n\n```typescript\nfunction cyclicSort(arr: number[]): void {\n let i: number = 0;\n while (i < arr.length) {\n const home: number = arr[i] - 1; // values 1..n\n if (arr[i] !== arr[home]) {\n [arr[i], arr[home]] = [arr[home], arr[i]];\n } else {\n i++;\n }\n }\n}\n```\n\n\nTwo implementation details:\n\n- The check is `arr[i] != arr[home]`, **not** `i != home`. This is what makes the algorithm safe in the presence of duplicates. When two indices hold the same value, the check stops further swapping and avoids an infinite loop.\n- `i` does not advance on a productive swap. The new value at position `i` might also be out of place, and the loop reprocesses it on the next iteration.\n\nFor the 0-to-n-1 variant, the only change is `int home = arr[i];`. For the missing-positive case (values 1 to n+1 with one missing), wrap the swap in a range check: `if (arr[i] > 0 && arr[i] <= n && arr[i] != arr[arr[i] - 1])`.\n\n---\n\n## Why O(n)\n\nThe outer loop body either advances `i` (O(1) work, happens at most n times) or performs a swap. Each swap places at least one value into its correct home position, and once a value is at home it stays there. So the total number of swaps across the entire run is at most `n - 1`. Total work: O(n).\n\nThe misleading visual is that the inner re-check looks like a nested loop. It is not. Across all iterations combined, the body runs at most `2n` times: at most `n` swaps plus at most `n` advances.\n\nThe space cost is O(1). All work happens in place via the swap.\n\n---\n\n## Applications\n\nSeveral LeetCode and interview classics reduce to \"run Cyclic Sort, then read the answer off the rearranged array in one scan.\" Each application below is a single pass on top of the sort.\n\n### Missing Number (LC 268)\n\nArray of length `n` contains `n` distinct integers from `0` to `n`. Find the missing one.\n\n\n```java\npublic static int missingNumber(int[] arr) {\n int n = arr.length, i = 0;\n while (i < n) {\n if (arr[i] < n && arr[i] != arr[arr[i]]) {\n int t = arr[i]; arr[i] = arr[t]; arr[t] = t;\n } else {\n i++;\n }\n }\n for (int j = 0; j < n; j++) {\n if (arr[j] != j) return j;\n }\n return n;\n}\n```\n\n\nThe sort places value `v` at index `v` (for the 0-indexed variant). The first index where `arr[j] != j` is the missing value. If every index matches, the missing value is `n`.\n\n### Find All Numbers Disappeared in an Array (LC 448)\n\nArray of length `n` with values from `1` to `n`, some duplicated. Find the values that never appear.\n\nAfter Cyclic Sort, scan for indices `j` where `arr[j] != j + 1`. Each such `j + 1` is a missing value.\n\n\n```java\npublic static List findDisappeared(int[] arr) {\n cyclicSort(arr);\n List missing = new ArrayList<>();\n for (int j = 0; j < arr.length; j++) {\n if (arr[j] != j + 1) missing.add(j + 1);\n }\n return missing;\n}\n```\n\n\n### Find All Duplicates in an Array (LC 442)\n\nSame array shape as LC 448, but report the duplicates instead. The duplicates are exactly the values that landed at the wrong index after Cyclic Sort. Scan and report `arr[j]` for each `j` where `arr[j] != j + 1`.\n\n### Find the Duplicate Number (LC 287)\n\nArray of length `n + 1` with values 1 to `n`, one duplicated. The duplicate is whatever value remains at index `i` after the loop cannot place it.\n\nOne caveat on LC 287: the problem statement disallows mutating the input, which rules out Cyclic Sort. Floyd's tortoise-and-hare cycle detection solves it without mutation. If mutation is allowed, Cyclic Sort solves it in one pass.\n\n### First Missing Positive (LC 41)\n\nArray of arbitrary integers, length `n`. Find the smallest positive integer that does not appear.\n\nThis is the hardest variant of the pattern. Values outside `[1, n]` are ignored during the swap. After sorting, the first index `j` where `arr[j] != j + 1` gives the answer `j + 1`. If every index matches, the answer is `n + 1`.\n\n\n```java\npublic static int firstMissingPositive(int[] arr) {\n int n = arr.length, i = 0;\n while (i < n) {\n int home = arr[i] - 1;\n if (arr[i] > 0 && arr[i] <= n && arr[i] != arr[home]) {\n int t = arr[i]; arr[i] = arr[home]; arr[home] = t;\n } else {\n i++;\n }\n }\n for (int j = 0; j < n; j++) {\n if (arr[j] != j + 1) return j + 1;\n }\n return n + 1;\n}\n```\n\n\nThe range check `arr[i] > 0 && arr[i] <= n` is the only addition. Negative values, zero, and values larger than `n` are skipped because they have no valid home in a length-`n` array.\n\n### Set Mismatch (LC 645)\n\nArray of length `n` with values 1 to `n` where one value is duplicated and one is missing. After Cyclic Sort, the index where `arr[j] != j + 1` gives both answers: the duplicated value is `arr[j]`, and the missing value is `j + 1`.\n\n---\n\n## Comparison with Alternatives\n\nFor arrays of the right shape (values 1 to n or 0 to n-1), Cyclic Sort dominates every alternative on the two metrics that matter together: time and space.\n\n\n| Approach | Time | Space | Notes |\n|----------|------|-------|-------|\n| **Cyclic Sort** | O(n) | O(1) | Optimal when values are in a dense range matching indices |\n| **Comparison sort** (Quick / Merge / Heap) | O(n log n) | O(1) to O(n) | Works on any input but wastes the structural assumption |\n| **Hash set** | O(n) | O(n) | Simple to write, doubles the memory |\n| **Counting sort** | O(n) | O(n) | Faster than comparison sort but still needs O(n) extra space |\n| **XOR trick** (single missing or single duplicate) | O(n) | O(1) | Elegant for exactly-one-of-each-kind variants, but does not generalize to \"find all missing / duplicates\" |\n| **Sign-flipping (mark visited)** | O(n) | O(1) | Mutates input by flipping signs. Often used as an alternative to Cyclic Sort for the same LeetCode set. |\n\n\nThe sign-flipping trick deserves a special mention. It uses the sign of `arr[arr[i] - 1]` as a \"visited\" bit. After processing, indices whose value is still positive correspond to missing values. Sign-flipping is O(n) time and O(1) space like Cyclic Sort, but it scrambles the values; Cyclic Sort produces the sorted array as a useful side effect.\n\n---\n\n## Common Pitfalls\n\n**Using **`i != home`** instead of **`arr[i] != arr[home]`**.** The first comparison is index-based and treats two indices holding the same value as if they were different, causing an infinite swap loop on duplicates.\n\n**Advancing **`i`** after a swap.** A productive swap can drop a new out-of-place value at index `i`. Advancing immediately leaves that value misplaced.\n\n**Forgetting the range check in the First Missing Positive variant.** Without `arr[i] > 0 && arr[i] <= n`, negative values cause negative indexing or array-out-of-bounds errors.\n\n**Confusing 0-indexed and 1-indexed variants.** Mixing `arr[i] - 1` and `arr[i]` in the same loop produces nonsense. Pick one variant for the problem at hand and document it in a comment.\n\n**Trying to use Cyclic Sort on arbitrary integers.** The algorithm depends on values mapping to indices. Arrays containing arbitrary integers, floats, or strings are not candidates. Confirm the value range matches the index range before applying the pattern.\n\n---\n\n## Complexity Analysis\n\n\n| Operation | Time | Space | Notes |\n|-----------|------|-------|-------|\n| Cyclic Sort (1..n or 0..n-1) | O(n) | O(1) | At most n - 1 swaps |\n| First Missing Positive | O(n) | O(1) | One extra scan after sorting |\n| Find All Missing / Duplicates | O(n) | O(1) extra (output excluded) | Single pass on top of the sort |\n| Stability | Not stable | | Duplicates are merged during swap |\n\n\nThe algorithm is unstable because the swap step does not respect the original relative order of equal values. For the standard applications this does not matter, as the output is either \"the sorted array\" or \"the list of missing / duplicate values,\" neither of which depends on stability.","pageType":"dsa"}

Cyclic Sort

Ashish Pratap Singh

Get Premium