Cyclic Sort Pattern

1. Place Elements in Correct Index

Concept	Rule	Invariant	Application
Index Mapping	For range [1,n]: place value k at index k-1	`arr[i] = i+1` after sorting	Numbers 1 to n in array of size n
Zero-based Range	For range [0,n-1]: place value k at index k	`arr[i] = i` after sorting	Numbers 0 to n-1 in array of size n
Swap Until Correct	Keep swapping until element at correct position	Each swap places at least one element correctly	O(n) time - each element moved once
Detection Phase	After sorting, scan for missing/duplicate	Incorrect position indicates problem	Missing numbers, duplicates, corrupt pairs

Example: Cyclic sort for range [1, n]

function cyclicSort(nums) {
    let i = 0;
    
    while (i < nums.length) {
        const correctIndex = nums[i] - 1; // For range [1,n]
        
        if (nums[i] !== nums[correctIndex]) {
            // Swap to place element at correct position
            [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
        } else {
            i++; // Element already at correct position
        }
    }
    
    return nums;
}

// [3, 1, 5, 4, 2] -> [1, 2, 3, 4, 5]
// Time: O(n), Space: O(1)
// Key insight: Each element swapped at most once

Example: Cyclic sort for range [0, n-1]

function cyclicSortZeroBased(nums) {
    let i = 0;
    
    while (i < nums.length) {
        const correctIndex = nums[i]; // For range [0,n-1]
        
        if (nums[i] < nums.length && nums[i] !== nums[correctIndex]) {
            [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
        } else {
            i++;
        }
    }
    
    return nums;
}

// [2, 0, 3, 1] -> [0, 1, 2, 3]

2. Find Missing Numbers O(n) Time

Problem Variant	Approach	Complexity	Key Insight
Single Missing	Cyclic sort then find index where arr[i] ≠ i+1	`O(n)`, `O(1)`	First incorrect position has missing number
All Missing	Cyclic sort then collect all incorrect positions	`O(n)`, `O(k)`	k missing numbers at wrong indices
Missing in Range	Place elements, scan for gaps	`O(n)`, `O(1)`	Expected value vs actual value mismatch
Without Modification	XOR or sum formula approach	`O(n)`, `O(1)`	Alternative when can't modify array

Example: Find missing number (single)

function findMissingNumber(nums) {
    let i = 0;
    const n = nums.length;
    
    // Cyclic sort for range [0, n]
    while (i < n) {
        const correctIndex = nums[i];
        
        if (nums[i] < n && nums[i] !== nums[correctIndex]) {
            [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
        } else {
            i++;
        }
    }
    
    // Find missing number
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i) {
            return i; // Missing number
        }
    }
    
    return n; // Missing number is n
}

// [3, 0, 1] -> 2
// [0, 1] -> 2
// [9,6,4,2,3,5,7,0,1] -> 8

Example: Find all missing numbers

function findDisappearedNumbers(nums) {
    let i = 0;
    
    // Cyclic sort for range [1, n]
    while (i < nums.length) {
        const correctIndex = nums[i] - 1;
        
        if (nums[i] !== nums[correctIndex]) {
            [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
        } else {
            i++;
        }
    }
    
    // Find all missing numbers
    const missing = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i + 1) {
            missing.push(i + 1);
        }
    }
    
    return missing;
}

// [4,3,2,7,8,2,3,1] -> [5,6]
// After sort: [1,2,3,2,3,8,7,8], positions 4,5 have wrong values

3. Find Duplicates O(1) Space Complexity

Detection Method	Strategy	Works For	Trade-off
Cyclic Sort Scan	After sorting, duplicate at wrong position	Range [1,n] with one duplicate	Modifies array
Swap Detection	During swap, if both same value = duplicate	Find during sort process	Early termination possible
Index Marking	Use sign to mark visited indices	Positive integers only	Reversible modification
Multiple Duplicates	Collect all positions with wrong values	Multiple duplicates present	Returns all duplicates

Example: Find duplicate number

function findDuplicate(nums) {
    let i = 0;
    
    while (i < nums.length) {
        const correctIndex = nums[i] - 1;
        
        if (nums[i] !== nums[correctIndex]) {
            [nums[i], nums[correctIndex]] = 
                [nums[correctIndex], nums[i]];
        } else {
            i++;
        }
    }
    
    // Find duplicate
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i + 1) {
            return nums[i];
        }
    }
    
    return -1;
}

// [1,3,4,2,2] -> 2

Example: Find all duplicates

function findDuplicates(nums) {
    let i = 0;
    
    while (i < nums.length) {
        const correctIndex = nums[i] - 1;
        
        if (nums[i] !== nums[correctIndex]) {
            [nums[i], nums[correctIndex]] = 
                [nums[correctIndex], nums[i]];
        } else {
            i++;
        }
    }
    
    const duplicates = [];
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i + 1) {
            duplicates.push(nums[i]);
        }
    }
    
    return duplicates;
}

Example: Find duplicates without modification (index marking)

function findDuplicatesIndexMarking(nums) {
    const duplicates = [];
    
    for (let i = 0; i < nums.length; i++) {
        const index = Math.abs(nums[i]) - 1;
        
        if (nums[index] < 0) {
            // Already negative - duplicate found
            duplicates.push(Math.abs(nums[i]));
        } else {
            // Mark as visited by negating
            nums[index] = -nums[index];
        }
    }
    
    // Restore array (optional)
    for (let i = 0; i < nums.length; i++) {
        nums[i] = Math.abs(nums[i]);
    }
    
    return duplicates;
}

// [4,3,2,7,8,2,3,1] -> [2,3]

4. Corrupt Pairs Detection Pattern

Problem Type	Definition	Detection	Solution
Set Mismatch	One number duplicated, one missing	Find both using cyclic sort	`[duplicate, missing]`
Corrupt Pair	Two numbers swapped incorrectly	Both positions have wrong values	Return the swapped pair
XOR Technique	Use XOR to find different elements	XOR all elements with expected range	Result is duplicate XOR missing
Sum Difference	Compare actual sum vs expected sum	Difference reveals relationship	Combined with product or sum of squares

Example: Find corrupt pair (set mismatch)

function findErrorNums(nums) {
    let i = 0;
    
    // Cyclic sort
    while (i < nums.length) {
        const correctIndex = nums[i] - 1;
        
        if (nums[i] !== nums[correctIndex]) {
            [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
        } else {
            i++;
        }
    }
    
    // Find duplicate and missing
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== i + 1) {
            return [nums[i], i + 1]; // [duplicate, missing]
        }
    }
    
    return [-1, -1];
}

// [1,2,2,4] -> [2,3] (2 is duplicate, 3 is missing)
// [1,1] -> [1,2]

5. First Missing Positive Integer Problem

Challenge	Solution	Key Insight	Complexity
Range Constraint	Only care about positives in [1, n]	Answer must be in [1, n+1]	Ignore negatives and > n
Cyclic Sort Modified	Sort only valid range values	Skip out-of-range during swap	`O(n)`, `O(1)`
First Gap	First index where arr[i] ≠ i+1	Missing positive at that index	Return index + 1
All Present Case	If [1..n] all present, answer is n+1	Perfect sequence means next is missing	Edge case handling

Example: First missing positive integer

function firstMissingPositive(nums) {
    let i = 0;
    const n = nums.length;
    
    // Cyclic sort - only for valid range [1, n]
    while (i < n) {
        const correctIndex = nums[i] - 1;
        
        // Only swap if value in valid range and not at correct position
        if (nums[i] > 0 && 
            nums[i] <= n && 
            nums[i] !== nums[correctIndex]) {
            [nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
        } else {
            i++;
        }
    }
    
    // Find first missing positive
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1) {
            return i + 1;
        }
    }
    
    // All [1..n] present, answer is n+1
    return n + 1;
}

// [1,2,0] -> 3
// [3,4,-1,1] -> 2
// [7,8,9,11,12] -> 1

Note: This is one of the hardest cyclic sort problems. The key is recognizing that the first missing positive must be in range [1, n+1], so we only need to consider elements in [1, n] during sorting.

6. Range Validation Techniques

Validation Type	Check	Purpose	Example
Bounds Check	`0 <= val < n` or `1 <= val <= n`	Prevent out-of-bounds access	Avoid array index errors
Duplicate Position	`nums[i] === nums[correctIndex]`	Detect when element already correct	Avoid infinite swap loops
Self-loop Prevention	`i !== correctIndex`	Don't swap element with itself	Optimization, not required
Valid Value Range	Filter out negatives, zeros, or too large	Skip irrelevant values	First missing positive problem

Example: Safe cyclic sort with validation

function safeCyclicSort(nums) {
    let i = 0;
    
    while (i < nums.length) {
        const val = nums[i];
        const correctIndex = val - 1;
        
        // Comprehensive validation
        if (val >= 1 &&                    // Lower bound
            val <= nums.length &&          // Upper bound
            val !== nums[correctIndex]) {  // Not duplicate
            
            [nums[i], nums[correctIndex]] = 
                [nums[correctIndex], nums[i]];
        } else {
            i++;
        }
    }
    
    return nums;
}

Example: Validation for edge cases

function validateAndSort(nums) {
    // Handle edge cases
    if (!nums || nums.length === 0) {
        return [];
    }
    
    if (nums.length === 1) {
        return nums;
    }
    
    let i = 0;
    while (i < nums.length) {
        const correctIndex = nums[i] - 1;
        
        if (correctIndex >= 0 &&
            correctIndex < nums.length &&
            nums[i] !== nums[correctIndex]) {
            [nums[i], nums[correctIndex]] = 
                [nums[correctIndex], nums[i]];
        } else {
            i++;
        }
    }
    
    return nums;
}

Cyclic Sort Pattern Summary

When to Use: Array contains numbers in range [1,n] or [0,n-1]
Core Pattern: Swap elements until each is at correct index position
Time Complexity: O(n) - each element moved at most once
Space Complexity: O(1) - in-place sorting
Applications: Missing numbers, duplicates, corrupt pairs
Key Validation: Check bounds and prevent duplicate swaps

Note: Cyclic sort achieves O(n) time with O(1) space by leveraging the property that array indices can store values. The pattern works because each swap places at least one element in its correct position, guaranteeing linear time.

Warning: Always validate before swapping: check nums[i] !== nums[correctIndex] to prevent infinite loops when duplicate exists. Ensure correctIndex is within bounds [0, n-1] to avoid out-of-bounds access. For first missing positive, skip values outside [1, n] range.