Cyclic Sort: Find Missing and Duplicate Numbers in O(n) Time, O(1) Space

Scenario context

If an array holds n numbers in range [1, n], each number belongs at index num - 1. Cyclic sort places every element at its correct index in O(n) time using O(1) space — then a single scan reveals every missing and duplicate number. Five interview problems, one technique.

---

Under the Hood: Internals of Cyclic Placement

The algorithm looks like it could be O(n²) — there is a while loop and each iteration…

This walkthrough focuses on Deep Dive: The Cycle Invariant and Why O(n) Holds Despite Nested Loops.

Before making a design choice, clarify:

• Under the Hood: Internals of Cyclic Placement The algorithm looks like it could be O(n²) — there is a while loop and each iteration may not advance i .
• But the key insight is that every swap permanently places at least one element at its correct index .
• Each element can be swapped into its correct position at most once.

Concepts in play: database-indexing, sorting-and-searching-algorithms, jvm-internals-and-garbage-collection, caching

Stage 1 — The Missing Number Challenge That Bans the Easy Solution

• Here is the exact constraint that forces cyclic sort into existence: "Given an array of n integers in the range [1, n], find all missing numbers — in O(n) time and O(1) space.
• You may not use a HashSet or any additional array." Without the O(1) space constraint, this is trivial: drop every number into a HashSet , then scan 1..n for gaps.
• That costs O(n) time and O(n) space.
• With the constraint, the HashSet is off the table.

Observable outcome: With the constraint, the HashSet is off the table.

Stage 2 — Index as Identity: The Invariant That Drives the Algorithm

• The invariant is deceptively simple: Number k belongs at index k − 1 .
• For an array [3, 1, 4, 2] (n = 4, range [1, 4]): After cyclic sort, every element sits at its correct index: [1, 2, 3, 4] .
• No mismatches — no missing numbers.
• For a missing number scenario like [3, 4, -1, 1] (where −1 is a placeholder for missing 2), the algorithm places what it can and leaves the slot for 2 empty (or containing a wrong value), revealing the gap.

Observable outcome: For a missing number scenario like [3, 4, -1, 1] (where −1 is a placeholder for missing 2), the algorithm places what it can and leaves the slot for 2 empty (or containing a wrong value), revealing the gap.

Stage 3 — The Cyclic Sort Algorithm: Place Every Number at Its Correct Index

• Walk the array from left to right.
• At each position i : - Compute the correct index for nums[i] : that is j = nums[i] - 1 .
• • If nums[i] != nums[j] (the number is not already at its correct home), swap nums[i] with nums[j] .
• • If nums[i] == nums[j] (either in place or a duplicate), advance i .

public class CyclicSort {

    // Core cyclic sort — places each number at index nums[i] - 1
    public void cyclicSort(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            int j = nums[i] - 1; // correct index for nums[i]
            if (nums[i] != nums[j]) {
                swap(nums, i, j); // send nums[i] to its correct home
            } else {
                i++; // nums[i] is in place (or duplicate) — advance
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

Observable outcome: - If nums[i] == nums[j] (either in place or a duplicate), advance i .

Stage 4 — Cyclic Placement Step by Step: Visualizing the Swap Cycle

• After the sort completes, every slot where nums[i] != i + 1 is a mismatch.
• The mismatch's index tells you which number is missing ( i + 1 ), and the mismatch's value tells you which number is a duplicate ( nums[i] ).

flowchart TD
    A[Start: i = 0] --> B[Compute j = nums[i] - 1]
    B --> C{nums[i] == nums[j]?}
    C -->|"No  wrong position"| D[Swap nums[i] with nums[j]]
    D --> B
    C -->|"Yes  in place or duplicate"| E[Advance: i++]
    E --> F{i < n?}
    F -->|Yes| B
    F -->|No| G[Cyclic sort complete]
    G --> H[Scan array for index-value mismatches]
    H --> I[Report missing / duplicate values]

Observable outcome: The mismatch's index tells you which number is missing ( i + 1 ), and the mismatch's value tells you which number is a duplicate ( nums[i] ).

Stage 5 — Real-World Applications: In-Place Array Mutation at Scale

• Deduplication pipelines in data engineering often process arrays of entity IDs (sequential integers assigned to database rows).
• When a batch of IDs in range [1, n] arrives and missing IDs indicate failed inserts, cyclic sort's O(1) space is critical — the data batch itself can be tens of millions of rows, and allocating an auxiliary array of equ…
• Embedded systems with severe memory constraints (microcontrollers, IoT firmware) use in-place algorithms where heap allocation is banned.
• Cyclic sort's zero-allocation pattern is a direct fit.

Observable outcome: Cyclic sort's zero-allocation pattern is a direct fit.

Stage 6 — When to Reach for Cyclic Sort

Observable outcome: You can explain how “When to Reach for Cyclic Sort” changes the architecture or implementation path.

End-to-end outcome

After working through the stages, you should be able to explain:

• • Core invariant : number k belongs at index k − 1 .
• After sorting, mismatches tell the whole story.

Alternatives considered

Cyclic Sort vs HashSet: When Space Actually Matters

The cyclic sort vs HashSet trade-off is not just academic: Cyclic sort is the right choice when: the input can be modified, random access is available (array, not stream), the O(1) space constraint is hard, and you need a single pattern that handles missing numbers, duplicates, and corrupt pairs uniformly.

Failure and degraded modes

Lessons from Cyclic Sort Pitfalls

• Detection: Lesson 1 — Forgetting the bounds check.
• User or operator impact: Lesson 1 — Forgetting the bounds check.