645 - Set Mismatch

Problem

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

Input: nums = [1,2,2,4]
Output: [2,3]

Input: nums = [1,1]
Output: [1,2]

Constraints:

• 2 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^4

Approach

Send every value v to index v - 1. The duplicate’s first copy claims its home slot; the second copy has nowhere of its own to go, so it ends up stranded in the one slot nobody claimed — which is exactly the missing number’s slot. That single mismatched position carries both answers:

• nums[j - 1] is the duplicate, the stranded second copy
• j is the missing number, the slot it is squatting in

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        const int n = nums.size();
        int i = 1;
        while (i <= n) {
            int corr = nums[i - 1];
            if (nums[corr - 1] != corr) {
                swap(nums[corr - 1], nums[i - 1]);
            } else {
                i++;
            }
        }

        for (int j = 1; j <= n; j++)
            if (nums[j - 1] != j) return {nums[j - 1], j};
        return {};
    }
};

nums = [3, 2, 3, 4, 6, 5]
i=1..4  every value already home          -> i advances each time
i=5     corr=6, nums[5]=5 != 6, swap      -> [3, 2, 3, 4, 5, 6]
i=5     corr=5, nums[4]=5 == 5            -> i=6
i=6     corr=6, nums[5]=6 == 6            -> i=7, stop

scan: j=1, nums[0]=3 != 1   ->  duplicate 3, missing 1  ->  [3, 1]

• time: O(n) — every swap puts one value permanently home, so at most n swaps in the whole loop
• space: O(1) — in place, though the input is rearranged