Set Mismatch
Problem
nums was originally [1, 2, ..., n] but one number got duplicated (replacing another). Return [duplicate, missing].
nums = [1, 2, 2, 4][2, 3]def find_error_nums(nums):
dup = -1
for x in nums:
i = abs(x) - 1
if nums[i] < 0:
dup = abs(x)
else:
nums[i] = -nums[i]
miss = -1
for i, v in enumerate(nums):
if v > 0:
miss = i + 1
break
return [dup, miss]function findErrorNums(nums) {
let dup = -1;
for (const x of nums) {
const i = Math.abs(x) - 1;
if (nums[i] < 0) dup = Math.abs(x);
else nums[i] = -nums[i];
}
let miss = -1;
for (let i = 0; i < nums.length; i++) {
if (nums[i] > 0) { miss = i + 1; break; }
}
return [dup, miss];
}class Solution {
public int[] findErrorNums(int[] nums) {
int dup = -1;
for (int x : nums) {
int i = Math.abs(x) - 1;
if (nums[i] < 0) dup = Math.abs(x);
else nums[i] = -nums[i];
}
int miss = -1;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) { miss = i + 1; break; }
}
return new int[]{dup, miss};
}
}vector<int> findErrorNums(vector<int>& nums) {
int dup = -1;
for (int x : nums) {
int i = abs(x) - 1;
if (nums[i] < 0) dup = abs(x);
else nums[i] = -nums[i];
}
int miss = -1;
for (int i = 0; i < (int)nums.size(); i++) {
if (nums[i] > 0) { miss = i + 1; break; }
}
return {dup, miss};
}Explanation
The array should hold 1..n but one value is duplicated and another is missing. The slick part of this solution is that it uses the array itself as a checklist by flipping signs — no extra hash map needed.
For each value x we look at index i = abs(x) - 1 (the slot that "belongs" to value x). If that slot is already negative, value x has been seen before, so x is the duplicate. Otherwise we mark the slot visited by negating it: nums[i] = -nums[i].
We use abs(x) because earlier steps may already have turned the value negative; the sign is just a "visited" flag, while the magnitude is the real number.
After the first pass, exactly one slot was never visited and stays positive. Its position i means the value i + 1 never appeared — that is the missing number.
Example: nums = [1,2,2,4]. Visiting marks slots for 1, 2, then we see 2 again (slot already negative) so dup = 2; slot for 4 gets marked. Index 2 stays positive, so missing = 3. Answer [2, 3].