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.

Related Cheat Sheets

Datastructures Algorithms

Mathematical Algorithms

Algorithm Patterns

Common Pitfalls and Edge Cases

Datastructures Algorithms

Algorithm Optimization and Performance

Algorithm Patterns

Modified Binary Search Patterns