Find the Corrupt Pair (One Duplicate and One Missing in 1..n)

• Corrupt Pair – an array of n values in 1..n has one duplicate and one missing; return both.
• Cyclic Sort – place each value v at index v-1; after placement, exactly one slot is mismatched.
• Mismatched slot – the stored value is the duplicate, and index+1 is the missing number.
• Algebraic alternative – use the difference of sums and squared sums to solve for both, but risks overflow.
• Complexity – O(n) time, O(1) extra space.

What is the Corrupt Pair problem?

An array of n numbers should hold each value from 1 to n exactly once, but due to corruption one number appears twice and another is missing. The task is to return both the duplicate and the missing number in O(n) time and O(1) extra space.

package com.bank.dsa;

public class CorruptPairFinder {
    // Returns [duplicate, missing]
    public int[] findCorruptPair(int[] nums) {
        // implementation below
        return new int[]{};
    }
}

How does Cyclic Sort solve this?

Run the Cyclic Sort placement loop with the duplicate-safe value-comparison guard. Because exactly one value is duplicated and exactly one is missing, precisely one slot ends up with nums[i] != i + 1 after placement. At that slot, nums[i] is the duplicate and i + 1 is the missing number.

package com.bank.dsa;

public class LedgerAuditor {
    public static int[] findCorruptPair(int[] ledger) {
        // Cyclic Sort placement
        int i = 0;
        while (i < ledger.length) {
            int home = ledger[i] - 1;
            if (ledger[i] != ledger[home]) {
                int temp = ledger[i];
                ledger[i] = ledger[home];
                ledger[home] = temp;
            } else {
                i++;
            }
        }

        // Find the mismatched slot
        for (int j = 0; j < ledger.length; j++) {
            if (ledger[j] != j + 1) {
                return new int[]{ledger[j], j + 1}; // [duplicate, missing]
            }
        }
        return new int[]{};
    }

    public static void main(String[] args) {
        int[] ledger = {3, 1, 2, 5, 2};
        int[] result = findCorruptPair(ledger);
        System.out.println("Duplicate: " + result[0] + ", Missing: " + result[1]);
    }
}

Duplicate: 2, Missing: 4

Why does exactly one slot end up mismatched?

The duplicate value occupies two slots in the input. During placement, the first copy goes to its home index. The second copy finds its home already occupied by the first copy (the value-comparison guard fires), so it stays stranded. The missing value's home slot is therefore occupied by the stranded duplicate, giving us both answers from one slot.

Input:  [3, 1, 2, 5, 2]  (n=5, duplicate=2, missing=4)
After:  [1, 2, 3, 2, 5]
                   ^--- slot 3: value=2, expected=4
                        duplicate=2, missing=4

How does the algebraic alternative work?

Compute the expected sum (1+2+...+n = n*(n+1)/2) and the actual sum. The difference gives duplicate - missing. Similarly, compute the expected and actual sums of squares. The difference of squared sums gives duplicate^2 - missing^2 = (duplicate + missing)(duplicate - missing). With both equations you can solve for both unknowns.

package com.bank.dsa;

public class AlgebraicCorruptPair {
    public static int[] findCorruptPair(int[] nums) {
        long n = nums.length;
        long expectedSum = n * (n + 1) / 2;
        long expectedSqSum = n * (n + 1) * (2 * n + 1) / 6;

        long actualSum = 0, actualSqSum = 0;
        for (int num : nums) {
            actualSum += num;
            actualSqSum += (long) num * num;
        }

        long diff = actualSum - expectedSum;       // dup - miss
        long sqDiff = actualSqSum - expectedSqSum; // dup^2 - miss^2
        long sumDupMiss = sqDiff / diff;            // dup + miss

        int duplicate = (int) ((diff + sumDupMiss) / 2);
        int missing = (int) ((sumDupMiss - diff) / 2);
        return new int[]{duplicate, missing};
    }
}

Why prefer Cyclic Sort over the algebraic approach?

Cyclic Sort is overflow-free because it only uses array swaps and index comparisons, never computing large sums. The algebraic approach requires sum and sum-of-squares computations that can overflow for large n even with long arithmetic. Cyclic Sort also reads more naturally, making it easier to explain under interview pressure.

| Approach | Overflow Risk | Readability | Time | Space |
|---|---|---|---|---|
| Cyclic Sort | None | High | O(n) | O(1) |
| Algebraic | Yes (large n) | Moderate | O(n) | O(1) |
| XOR-based | None | Low | O(n) | O(1) |

What are edge cases?

Edge cases include the duplicate being 1 (the smallest value), the duplicate being n (the largest value), and the missing being 1 or n. All cases result in exactly one mismatched slot after placement.

findCorruptPair(new int[]{1, 1});       // [1, 2]
findCorruptPair(new int[]{2, 2});       // [2, 1]
findCorruptPair(new int[]{2, 3, 3});    // [3, 1]

What are common mistakes?

The most common mistake is returning i + 1 as the duplicate and nums[i] as the missing, which swaps the two answers. Remember: the stored value is the duplicate (it is the extra copy), and the index+1 is the missing (the slot that was supposed to hold it).

// Wrong: swapped
return new int[]{j + 1, ledger[j]}; // [missing, duplicate]

// Correct:
return new int[]{ledger[j], j + 1}; // [duplicate, missing]

What should a senior engineer know?

A senior engineer recognises this as the natural combination of Find the Duplicate and Find the Missing in a single Cyclic Sort pass. They present both the Cyclic Sort and algebraic approaches, explain the overflow trade-off, and pick Cyclic Sort for interviews. They also mention the XOR-based approach as a third option that is overflow-free but harder to explain.