Set Mismatch
Last Updated: March 29, 2026
Understanding the Problem
We have an array that should contain every integer from 1 to n exactly once, but something went wrong. One number appears twice, and because of that, another number is missing entirely. Our job is to find both: the duplicate and the missing number.
The constraint 1 <= nums[i] <= nums.length is important. It tells us every value in the array is within the range [1, n], which means we can use the values themselves as indices. This is the key observation that unlocks the most elegant solutions.
A brute force approach would count occurrences of every number. But we can do better by exploiting the relationship between the values and the index range [1, n]. Techniques like sorting, hashing, sum/sum-of-squares math, and index marking all become viable because of this tight value-to-index mapping.
Key Constraints:
2 <= nums.length <= 10^4— With n up to 10,000, O(n^2) means 100 million operations, which is borderline. O(n log n) and O(n) approaches are both comfortable.1 <= nums[i] <= nums.length— Every value maps directly to a valid index in the range [1, n]. This enables index-marking techniques and mathematical approaches.
Approach 1: Sorting
Intuition
The most straightforward way to spot a duplicate is to sort the array first. Once sorted, duplicate numbers sit next to each other, and a gap in the sequence reveals the missing number. This is the approach you'd naturally reach for if someone handed you a shuffled deck of numbered cards and asked you to find the repeated and missing one.
Algorithm
- Sort the array in ascending order.
- Check if the first element is 1. If not, the missing number is 1.
- Iterate through the sorted array from index 1 to n-1.
- If
nums[i] == nums[i-1], we found the duplicate. - If
nums[i] > nums[i-1] + 1, the missing number isnums[i-1] + 1. - After the loop, if
missingis still not found, the missing number must be n. - Return
[duplicate, missing].
Example Walkthrough
Input:
After sorting (already sorted in this case), we scan adjacent pairs:
nums[1]=2 == nums[0]=1— no match, no gapnums[2]=2 == nums[1]=2— duplicate found!duplicate = 2nums[3]=4 > nums[2]=2 + 1— gap!missing = 3
Result:
Code
- Time Complexity: O(n log n). Sorting dominates at O(n log n). The subsequent linear scan is O(n), which gets absorbed.
- Space Complexity: O(1) or O(log n). No extra data structures, ignoring the internal stack space used by sorting algorithms.
This approach works but sorting gives us more information than we need. What if we just counted how many times each number appears?
Approach 2: Hash Map Counting
Intuition
Instead of sorting to detect duplicates and gaps, we can just count how many times each number appears. Build a frequency map in one pass, then scan numbers 1 through n. The number with count 2 is the duplicate, and the number with count 0 is the missing one.
This is the approach most people would write in production. It's clean, obvious, and hard to get wrong.
Since every number from 1 to n should appear exactly once, any deviation from a count of 1 reveals the error. A count of 2 means that number was duplicated, and a count of 0 means that number was overwritten and is now missing. The hash map lets us compute all counts in O(n), and the second pass over [1, n] lets us identify both anomalies.
Algorithm
- Create a hash map and count occurrences of each number in the array.
- Iterate through numbers 1 to n.
- If a number has count 2, it's the duplicate.
- If a number has count 0 (not in the map), it's the missing number.
- Return
[duplicate, missing].
Example Walkthrough
Code
- Time Complexity: O(n). One pass to build the frequency map, one pass over [1, n] to find the duplicate and missing. Both are O(n).
- Space Complexity: O(n). The hash map stores up to n entries.
The hash map uses O(n) extra space. Since every value maps to a valid index in [1, n], can we use the array itself as our visited tracker?
Approach 3: Negative Marking (Optimal)
Intuition
Since every value in the array is between 1 and n, we can use each value as an index into the array itself. When we visit a number, we negate the value at the corresponding index to "mark" it as seen. If we try to mark an index that's already negative, we've found the duplicate. After the marking pass, the index that still holds a positive value corresponds to the missing number.
This is essentially using the input array as a boolean visited array, with the sign bit serving as the flag. It's O(n) time and O(1) extra space.
The sign of nums[i] encodes whether the number i+1 has been "seen" in the array. In a correct array [1, n], every index from 0 to n-1 would get negated exactly once. When one number is duplicated, its corresponding index gets negated twice (the second time, it's already negative, revealing the duplicate). And because the missing number was never in the array, its corresponding index never gets negated, staying positive.
Algorithm
- Iterate through the array. For each element, compute the target index as
abs(nums[i]) - 1. - Check the value at
nums[targetIndex]. If it's already negative, thenabs(nums[i])is the duplicate. - Otherwise, negate
nums[targetIndex]to mark it as visited. - After the first pass, iterate through the array again. The index where
nums[index] > 0corresponds to the missing number (which isindex + 1). - Return
[duplicate, missing].
Example Walkthrough
Code
- Time Complexity: O(n). Two passes through the array: one for marking, one for finding the missing number. Each is O(n).
- Space Complexity: O(1). Only a constant number of extra variables. The marking is done in place by modifying the input array.