Pattern 06: Cyclic Sort

0. The Template (Copy-Paste Skeleton)

The trigger is narrow but unmistakable: n numbers drawn from the range 1..n (or 0..n-1), and the interviewer wants O(1) extra space. The array itself becomes the hash table.

// TEMPLATE A — CYCLIC SORT (place every value at its own index)
void cyclicSort(int[] nums) {
    int i = 0;
    while (i < nums.length) {
        int correct = nums[i] - 1;              // for 1..n. For 0..n-1 use: int correct = nums[i];
        if (nums[i] != nums[correct]) {         // compare VALUES, not indices — handles duplicates
            swap(nums, i, correct);             // do NOT advance i — the swapped-in value is unchecked
        } else {
            i++;                                // already home (or a duplicate) → move on
        }
    }
}
// Afterwards: the first index where nums[i] != i + 1 is your missing / duplicate / mismatch.

// TEMPLATE B — NEGATIVE MARKING (mark presence in place, values are positive)
for (int x : nums) {
    int idx = Math.abs(x) - 1;
    if (nums[idx] > 0) nums[idx] = -nums[idx];   // "I have seen the value idx+1"
}
for (int i = 0; i < nums.length; i++) {
    if (nums[i] > 0) missing.add(i + 1);         // never marked ⇒ absent
}

// TEMPLATE C — XOR (exactly one unpaired element)
int single = 0;
for (int x : nums) single ^= x;    // a^a == 0, a^0 == a → pairs cancel, the loner survives
return single;

The one rule that breaks everyone

Do not i++ after a swap. The value you just swapped into position i has not been checked yet. Only advance when the element at i is already correct.

Why it’s O(n) despite the while + swap

Every swap puts at least one value into its final position permanently. A value is never moved out of a correct slot, so there are at most n swaps in total across the whole run.

Which variant?

Problem shape	Template
find the missing / duplicate number in 1..n	A
find all numbers disappeared / all duplicates	A or B
“set mismatch” (one duplicated, one missing)	A
every element appears twice except one	C (XOR)
first missing positive (unbounded values)	A, ignoring anything outside 1..n
find the duplicate without modifying the array	Floyd’s cycle → 04-Fast-And-Slow-Pointers

---

1. Pattern Identification & Logic

How to Identify (Interview Triggers)

• Array contains numbers in the range 1 to N (or 0 to N)
• “Find the missing number” or “find the duplicate”
• “Find all missing/duplicate numbers”
• Input constraint: numbers are bounded by array length
• O(1) extra space required

The Algorithm (Pseudocode)

i = 0
while (i < n):
    correctIndex = nums[i] - 1   // where this number should be

    if nums[i] != nums[correctIndex]:
        swap(nums[i], nums[correctIndex])
    else:
        i++

// After sorting, any nums[i] != i+1 is a missing/duplicate

The ‘Trick’ to Know

• Each number is swapped at most once to its correct position, so total swaps are O(n) despite the while loop.
• When you encounter a duplicate during swapping (nums[i] == nums[correctIndex] but i != correctIndex), that’s your duplicate.

---

2. Java Implementation (Brute Force vs. Optimal)

Example Problem: Find the Missing Number - LC 268

Brute Force: Sorting - O(n log n)

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) return i;
        }
        return nums.length;
    }
}

Optimal: Cyclic Sort - O(n) time, O(1) space

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0;
        int n = nums.length;

        while (i < n) {
            int correctIdx = nums[i];
            if (nums[i] < n && nums[i] != nums[correctIdx]) {
                int temp = nums[i];
                nums[i] = nums[correctIdx];
                nums[correctIdx] = temp;
            } else {
                i++;
            }
        }

        for (i = 0; i < n; i++) {
            if (nums[i] != i) return i;
        }
        return n;
    }
}

Java Architecture Insights

• In-place swap: Java has no built-in swap. Always use a temp variable. Don’t use XOR swap in interviews - it’s error-prone and less readable.
• Bounds check nums[i] < n: Critical because the missing number means one value equals n, which would be out of bounds.
• Alternative: Math formula n*(n+1)/2 - sum works for missing number but doesn’t extend to finding duplicates or multiple missing numbers.

---

3. Mental Model & Visualization

ASCII Diagram (nums = [3, 0, 1])

Start:   [3, 0, 1]    i=0

i=0: nums[0]=3, correctIdx=3 → out of bounds (3 >= n=3), skip → i=1
i=1: nums[1]=0, correctIdx=0, nums[0]=3 ≠ 0 → swap → [0, 3, 1], i stays
i=1: nums[1]=3, correctIdx=3 → out of bounds, skip → i=2
i=2: nums[2]=1, correctIdx=1, nums[1]=3 ≠ 1 → swap → [0, 1, 3], i stays
i=2: nums[2]=3, correctIdx=3 → out of bounds, skip → i=3

Result: [0, 1, 3]
Check: nums[0]=0 ✓, nums[1]=1 ✓, nums[2]=3 ≠ 2 → missing = 2

Senior Mental Trigger

“Numbers in range 1..N + find missing/duplicate = place each number at its correct index.”

---

4. Curated Problem Lists

Commonly Asked (Bread & Butter)

#	Problem	Difficulty
LC 268	Missing Number	Easy
LC 448	Find All Numbers Disappeared	Easy
LC 41	First Missing Positive	Hard
LC 136	Single Number	Easy
LC 645	Set Mismatch	Easy

FAANG ‘Aha!’ Level (Hard/Unintuitive)

#	Problem	Difficulty
LC 287	Find the Duplicate Number	Medium
LC 442	Find All Duplicates in an Array	Medium
LC 765	Couples Holding Hands	Hard
LC 41	First Missing Positive	Hard
LC 1539	Kth Missing Positive Number	Easy

---

5. Time & Space Complexity Table

Approach	Time	Space	Notes
Sorting	O(n log n)	O(1)	Sort then scan
HashSet	O(n)	O(n)	Store all, check missing
Cyclic Sort	O(n)	O(1)	In-place, each element swapped once
Math Formula	O(n)	O(1)	Only for single missing number