Cyclic Sort - rFronteddu/general_wiki GitHub Wiki

When: Numbers in range [1…N] Use cases:

• Find missing number
• Find duplicates
• First missing positive

Cyclic Sort typically applies when:

• numbers are in range [1..n] or [0..n]
• and the goal is to place each number at its correct index.

Correct index formulas:

• value v in [1..n] -> index = v - 1
• value v in [0..n] -> index = v

Easy

• Missing Number = Find the missing number in [0..n].
• Find All Numbers Disappeared in an Array Numbers are [1..n]. Some missing.
• Find the Duplicate Number One number repeated.
• Set Mismatch One duplicated and one missing.
• Find All Duplicates in an Array
• Third Maximum Number Not pure cyclic sort but useful practice.

Medium (Classic Cyclic Sort)

• First Missing Positive One of the most important cyclic-sort problems.
• Find the Smallest Missing Positive Number Classic pattern variant.
• Kth Missing Positive Number
• Find Missing Observations
• Restore the Array From Adjacent Pairs
• [Corrupt Pair Problem](Set Mismatch) Duplicate + missing pair.
• [Missing Number II](Missing Number)

Hard (Advanced Variants) - These require cyclic-sort reasoning combined with other techniques.

• First Missing Positive (considered hard because of constraints)
• Recover the Original Array
• Find Missing and Repeated Values
• Array Nesting Uses index-placement logic.
• Couples Holding Hands Uses swap-to-correct-position logic.
• Minimum Swaps to Arrange a Binary Grid Swap-based positioning idea.
• Minimum Number of Swaps to Make the String Balanced Conceptually similar swap reasoning.

Must known:

• Missing Number
• Find All Numbers Disappeared in an Array
• Find All Duplicates in an Array
• Set Mismatch
• Find the Duplicate Number
• First Missing Positive

The 4 Core Cyclic Sort Interview Patterns

Pattern 1 — Missing number

Problems:

• #268
• #448
• #1539

Pattern 2 — Duplicate numbers

Problems:

• #442
• #287

Pattern 3 — Missing + duplicate pair

Problems:

• #645
• #2965

Pattern 4 — First missing positive

Problems:

• #41

The Core Cyclic Sort Template

int i = 0;

while(i < nums.size()) {
    int correct = nums[i] - 1;

    if(nums[i] != nums[correct])
        swap(nums[i], nums[correct]);
    else
        i++;
}

Then scan for mismatches.

The key condition for Cyclic Sort:

• Numbers are in a bounded range
• [1..n] or [0..n] Then you swap numbers into their correct index.