Cyclic Sort Pattern¶

Overview¶

When given an array containing numbers in a range [1, n] or [0, n], place each number at its correct index using cyclic swaps. Useful for finding missing/duplicate numbers in O(n) time and O(1) space.

When to Use¶

Array with numbers in range [0, n] or [1, n]
Find missing number(s)
Find duplicate number(s)
Find first missing positive
Problems requiring O(1) space with range-limited numbers

Cyclic Sort Visualization

Template Code¶

Basic Cyclic Sort¶

public void cyclicSort(int[] nums) {
    int i = 0;

    while (i < nums.length) {
        int correctIndex = nums[i] - 1;  // For [1, n]

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

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

Find Missing Number (0 to n)¶

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

    while (i < n) {
        // For [0, n], correct index = nums[i]
        if (nums[i] < n && nums[i] != i) {
            swap(nums, i, nums[i]);
        } else {
            i++;
        }
    }

    // Find the missing number
    for (i = 0; i < n; i++) {
        if (nums[i] != i) {
            return i;
        }
    }
    return n;  // All 0 to n-1 present, so n is missing
}

Find All Missing Numbers¶

public List<Integer> findDisappearedNumbers(int[] nums) {
    int i = 0;

    while (i < nums.length) {
        int correctIndex = nums[i] - 1;  // For [1, n]

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

    List<Integer> missing = new ArrayList<>();
    for (i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            missing.add(i + 1);
        }
    }
    return missing;
}

Find Duplicate Number¶

public int findDuplicate(int[] nums) {
    int i = 0;

    while (i < nums.length) {
        if (nums[i] != i + 1) {
            int correctIndex = nums[i] - 1;

            if (nums[i] != nums[correctIndex]) {
                swap(nums, i, correctIndex);
            } else {
                return nums[i];  // Found duplicate!
            }
        } else {
            i++;
        }
    }
    return -1;
}

Find All Duplicates¶

public List<Integer> findDuplicates(int[] nums) {
    int i = 0;

    while (i < nums.length) {
        int correctIndex = nums[i] - 1;

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

    List<Integer> duplicates = new ArrayList<>();
    for (i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            duplicates.add(nums[i]);
        }
    }
    return duplicates;
}

First Missing Positive¶

public int firstMissingPositive(int[] nums) {
    int n = nums.length;
    int i = 0;

    while (i < n) {
        int correctIndex = nums[i] - 1;

        // Only handle positive numbers in range [1, n]
        if (nums[i] > 0 && nums[i] <= n && nums[i] != nums[correctIndex]) {
            swap(nums, i, correctIndex);
        } else {
            i++;
        }
    }

    // Find first missing positive
    for (i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return i + 1;
        }
    }
    return n + 1;
}

Find Corrupt Pair (Missing and Duplicate)¶

public int[] findErrorNums(int[] nums) {
    int i = 0;

    while (i < nums.length) {
        int correctIndex = nums[i] - 1;

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

    // Find the corrupt pair
    for (i = 0; i < nums.length; i++) {
        if (nums[i] != i + 1) {
            return new int[]{nums[i], i + 1};  // [duplicate, missing]
        }
    }
    return new int[]{-1, -1};
}

Find First K Missing Positive Numbers¶

public List<Integer> findKMissingPositive(int[] nums, int k) {
    int n = nums.length;
    int i = 0;

    // Cyclic sort for numbers in [1, n]
    while (i < n) {
        int correctIndex = nums[i] - 1;

        if (nums[i] > 0 && nums[i] <= n && nums[i] != nums[correctIndex]) {
            swap(nums, i, correctIndex);
        } else {
            i++;
        }
    }

    List<Integer> missing = new ArrayList<>();
    Set<Integer> extraNumbers = new HashSet<>();

    // Find missing in [1, n]
    for (i = 0; i < n && missing.size() < k; i++) {
        if (nums[i] != i + 1) {
            missing.add(i + 1);
            extraNumbers.add(nums[i]);
        }
    }

    // Find missing beyond n
    int candidate = n + 1;
    while (missing.size() < k) {
        if (!extraNumbers.contains(candidate)) {
            missing.add(candidate);
        }
        candidate++;
    }

    return missing;
}

Alternative: Marking Approach (Without Swapping)¶

// Use sign to mark visited indices
public List<Integer> findDisappearedNumbersMarking(int[] nums) {
    // Mark indices as visited by negating
    for (int i = 0; i < nums.length; i++) {
        int index = Math.abs(nums[i]) - 1;
        if (nums[index] > 0) {
            nums[index] = -nums[index];
        }
    }

    // Positive indices indicate missing numbers
    List<Integer> missing = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            missing.add(i + 1);
        }
    }

    return missing;
}

Time & Space Complexity¶

Problem	Time	Space
Cyclic sort	O(n)	O(1)
Missing number	O(n)	O(1)
All missing numbers	O(n)	O(1)*
Duplicate number	O(n)	O(1)
All duplicates	O(n)	O(1)*
First missing positive	O(n)	O(1)

*Output space not counted

Common Interview Questions¶

Missing Number - One missing in [0, n]
Find All Numbers Disappeared - Multiple missing in [1, n]
Find the Duplicate Number - One duplicate in [1, n]
Find All Duplicates - Multiple duplicates in [1, n]
Set Mismatch - Find duplicate and missing
First Missing Positive - First positive not in array
Find K Missing Positive - First K missing positives
Couples Holding Hands - Variation of cyclic sort

Tips & Tricks¶

For range [1, n]: correct index = nums[i] - 1
For range [0, n-1]: correct index = nums[i]
Always check bounds before swapping
Swap while incorrect, not just once
After sorting, misplaced elements reveal missing/duplicates
Marking approach works if you can't modify structure
This pattern achieves O(n) time, O(1) space without sorting!