Cyclic Sort: Patterns

March 2026 · 16 min read

The core cyclic sort technique handles the basic missing-number and duplicate problems. This post covers three harder patterns that build on the same idea: place each number at its correct index, then read the answer from the mismatches.

Pattern 1: Find the Corrupt Pair

Problem: An array of n numbers in the range [1, n] has one number replaced by another. This means there is exactly one duplicate and exactly one missing number. Find both.

This is a direct extension of cyclic sort. After placing every value at its correct index, exactly one slot will hold the wrong value. That slot reveals both answers at once: the value sitting there is the duplicate, and the index that should have been there tells you the missing number.

Step-by-Step

Visual Walkthrough

Array: [3, 1, 2, 5, 2]. After cyclic sort: [1, 2, 3, 2, 5].

Interactive Animation

C++ Implementation

std::pair<int,int> findCorruptPair(std::vector<int>& nums) {
    int n = nums.size();
    int i = 0;
    while (i < n) {
        int correct = nums[i] - 1;
        if (nums[i] != nums[correct]) {
            std::swap(nums[i], nums[correct]);
        } else {
            i++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return {nums[i], i + 1}; // {duplicate, missing}
        }
    }
    return {-1, -1};
}

// Example: [3, 1, 2, 5, 2]
// After sort: [1, 2, 3, 2, 5]
// Index 3: arr[3]=2 != 4  =>  duplicate=2, missing=4

Pattern 2: First Missing Positive

Problem: Given an unsorted integer array (can contain negatives and zeros), find the smallest missing positive integer. This must run in $O(n)$ time and $O(1)$ extra space.

This is the hardest cyclic sort variant and a classic hard interview question. The key observation: for an array of length n, the first missing positive must be in $[1, n+1]$. By the pigeonhole principle, if all values 1 through n are present, the answer is $n+1$. Otherwise, some value in $[1, n]$ is missing, and we can find it with cyclic sort.

The Trick

Ignore values outside [1, n]. Negatives, zeros, and anything greater than n cannot affect which positive integer in [1, n] is missing. Treat the array as slots for values 1 through n and swap only valid positives into place.

Visual Walkthrough

Array: [3, 4, -1, 1]. Length n = 4, so first missing positive is in [1, 5].

C++ Implementation

int firstMissingPositive(std::vector<int>& nums) {
    int n = nums.size();
    int i = 0;
    while (i < n) {
        int correct = nums[i] - 1;
        // Only swap if value is in [1, n] and not already correct
        if (nums[i] >= 1 && nums[i] <= n
            && nums[i] != nums[correct]) {
            std::swap(nums[i], nums[correct]);
        } else {
            i++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;
}

// Example: [3, 4, -1, 1]
// After sort: [1, -1, 3, 4]
// Index 1: arr[1]=-1 != 2  =>  answer is 2

// Example: [7, 8, 9, 11, 12]
// After sort: [7, 8, 9, 11, 12]  (nothing in [1,5])
// Index 0: arr[0]=7 != 1  =>  answer is 1

Second Example

Array: [1, 2, 3]. After sort: [1, 2, 3]. All slots match. Answer: $n + 1 = 4$.

Pattern 3: Set Mismatch

Problem (LeetCode 645): The set S originally contains numbers from 1 to n. Due to a data error, one of the numbers got duplicated to another, resulting in one repeated number and one missing number. Return the repeated number and the missing number.

This is essentially the same structural problem as the corrupt pair, but it appears frequently enough under the name "Set Mismatch" that it deserves its own section. The cyclic sort approach is identical, but let us also explore two alternative methods that avoid modifying the array.

Approach 1: Cyclic Sort

Identical to the corrupt pair solution. Sort, scan, report.

Visual Walkthrough

Array: [1, 2, 2, 4]. After cyclic sort: [1, 2, 2, 4].

std::vector<int> findErrorNums(std::vector<int>& nums) {
    int n = nums.size();
    int i = 0;
    while (i < n) {
        int correct = nums[i] - 1;
        if (nums[i] != nums[correct]) {
            std::swap(nums[i], nums[correct]);
        } else {
            i++;
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) {
            return {nums[i], i + 1}; // {duplicate, missing}
        }
    }
    return {};
}

// Example: [1, 2, 2, 4]
// After sort: [1, 2, 2, 4]
// Index 2: arr[2]=2 != 3  =>  duplicate=2, missing=3

Approach 2: Math (No Array Modification)

Use two equations. Let d be the duplicate and m be the missing number.

std::vector<int> findErrorNumsMath(std::vector<int>& nums) {
    long n = nums.size();
    long sumDiff = 0, sqDiff = 0;
    for (long i = 0; i < n; i++) {
        sumDiff += nums[i] - (i + 1);
        sqDiff += (long)nums[i] * nums[i] - (i + 1) * (i + 1);
    }
    // sumDiff = d - m, sqDiff = d^2 - m^2 = (d-m)(d+m)
    long sumOfBoth = sqDiff / sumDiff; // d + m
    int dup = (int)((sumDiff + sumOfBoth) / 2);
    int missing = (int)(dup - sumDiff);
    return {dup, missing};
}

// Example: [1, 2, 2, 4], n=4
// sumDiff = (1+2+2+4) - (1+2+3+4) = 9 - 10 = -1 = d - m
// sqDiff = (1+4+4+16) - (1+4+9+16) = 25 - 30 = -5 = d^2 - m^2
// d + m = -5 / -1 = 5, d = (-1+5)/2 = 2, m = 2-(-1) = 3

Approach 3: XOR (No Array Modification)

XOR all array elements with all numbers 1 to n. The result is d XOR m. Use any differing bit to split numbers into two groups and XOR each group separately to isolate d and m.

std::vector<int> findErrorNumsXOR(std::vector<int>& nums) {
    int n = nums.size();
    int xorAll = 0;
    for (int i = 0; i < n; i++) {
        xorAll ^= nums[i] ^ (i + 1);
    }
    // xorAll = d ^ m (they differ in at least one bit)
    int diffBit = xorAll & (-xorAll); // lowest set bit

    int group0 = 0, group1 = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] & diffBit) group1 ^= nums[i];
        else group0 ^= nums[i];
        if ((i + 1) & diffBit) group1 ^= (i + 1);
        else group0 ^= (i + 1);
    }
    // One group holds d, the other holds m. Check which is which.
    for (int x : nums) {
        if (x == group0) return {group0, group1};
    }
    return {group1, group0};
}

Pattern Summary

Key Takeaways

• The corrupt pair and set mismatch are structurally identical. After cyclic sort, the mismatched index reveals both the duplicate and the missing number in one scan.
• First missing positive extends cyclic sort by filtering out-of-range values. The answer is always in $[1, n+1]$ by the pigeonhole principle.
• For set mismatch, the math approach (sum and sum of squares) and the XOR approach both avoid modifying the input array. Know all three for interviews.
• All three patterns run in $O(n)$ time and $O(1)$ extra space with cyclic sort.