Set Mismatch
EasyPrompt
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.
Example 1:
Input: nums = [1,2,2,4]
Output: [2,3]Example 2:
Input: nums = [1,1]
Output: [1,2]
Constraints:
2 <= nums.length <= 1041 <= nums[i] <= 104
Approaches
4 approaches with complexity analysis and trade-offs.
This is the most straightforward and intuitive approach. We can iterate through all numbers from 1 to n (where n is the length of the array). For each number, we perform another iteration through the input array nums to count its occurrences.
Algorithm
- Get the size of the array,
n. - Initialize
duplicate = -1andmissing = -1. - Loop
ifrom 1 ton. - Inside the loop, initialize a counter
count = 0. - Start an inner loop through each
numin thenumsarray. - If
num == i, incrementcount. - After the inner loop finishes, check the value of
count. - If
count == 2, it meansiis the duplicated number, so setduplicate = i. - If
count == 0, it meansiis the missing number, so setmissing = i. - After the outer loop finishes, return the array
[duplicate, missing].
Walkthrough
The method involves a nested loop structure. The outer loop iterates through each number i that is expected to be in the set, from 1 to n. For each of these numbers, the inner loop traverses the entire nums array to count how many times i appears. By the definition of the problem, one number will appear twice (its count will be 2), and one number will not appear at all (its count will be 0). We use two variables, duplicate and missing, to keep track of these numbers as we find them. After checking all numbers from 1 to n, we will have identified both the duplicate and the missing value.
class Solution { public int[] findErrorNums(int[] nums) { int n = nums.length; int duplicate = -1; int missing = -1; for (int i = 1; i <= n; i++) { int count = 0; for (int num : nums) { if (num == i) { count++; } } if (count == 2) { duplicate = i; } else if (count == 0) { missing = i; } } return new int[]{duplicate, missing}; }}Complexity
Time
O(n^2), where n is the number of elements in the `nums` array. The outer loop runs `n` times, and for each iteration, the inner loop also runs `n` times.
Space
O(1), as we only use a few constant extra variables to store the result and the counter.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space, aside from the result array.
Cons
Extremely inefficient with a time complexity of O(n^2).
Will likely result in a 'Time Limit Exceeded' error on most online judges for larger inputs.
A more efficient approach involves trading space for time. We can use a hash map (or a frequency array, since the numbers are within a specific range) to count the occurrences of each number in the input array. This eliminates the need for the costly nested loop.
Algorithm
- Create a
HashMap<Integer, Integer>to store the frequency of each number. - Iterate through the input array
nums. For eachnum, update its count in the hash map. - Initialize
duplicate = -1andmissing = -1. - Get the size of the array,
n. - Iterate from
i = 1ton. - For each
i, check its presence and count in the hash map. - If
map.get(i)is 2, theniis the duplicate number. - If
map.get(i)is null (or the keyidoes not exist), theniis the missing number. - Return the
[duplicate, missing]array.
Walkthrough
First, we traverse the nums array once, populating a hash map where keys are the numbers from the array and values are their frequencies. This gives us a count of each number in O(n) time.
Next, we iterate through the numbers from 1 to n. For each number i, we query the hash map. If the map indicates that the frequency of i is 2, we have found our duplicate. If the map does not contain the key i, it means i was never present in the input array, making it the missing number. This second loop also takes O(n) time, leading to an overall linear time complexity.
import java.util.HashMap;import java.util.Map; class Solution { public int[] findErrorNums(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); int duplicate = -1; int missing = -1; int n = nums.length; for (int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); } for (int i = 1; i <= n; i++) { if (map.containsKey(i)) { if (map.get(i) == 2) { duplicate = i; } } else { missing = i; } } return new int[]{duplicate, missing}; }}Complexity
Time
O(n). We iterate through the `nums` array once to build the map and then iterate from 1 to `n` once to find the result. This is O(n + n) = O(n).
Space
O(n), as the hash map can store up to `n-1` key-value pairs in the worst case.
Trade-offs
Pros
Significantly more efficient than the brute-force approach with a linear time complexity.
The logic is straightforward and easy to follow.
Cons
Requires extra space proportional to the number of unique elements in the array, which can be O(n).
A highly efficient approach with optimal time and space complexity involves using the input array itself as a data structure to track seen numbers. Since the numbers are in the range [1, n], we can map each number k to the array index k-1. We mark a number as 'seen' by negating the value at its corresponding index.
Algorithm
- Initialize
duplicate = -1andmissing = -1. - Iterate through the
numsarray. For eachnum:- Calculate the corresponding index:
index = Math.abs(num) - 1. - Check the sign of the element at this index,
nums[index]. - If
nums[index]is negative, it means the numberMath.abs(num)has been seen before. This is our duplicate. Store it in theduplicatevariable. - If
nums[index]is positive, negate it (nums[index] *= -1) to mark that we have now seen the numberMath.abs(num).
- Calculate the corresponding index:
- After the first pass, the duplicate is found. Now, find the missing number.
- Iterate through the modified
numsarray fromi = 0ton-1. - The first index
iwhere the elementnums[i]is still positive corresponds to the missing number,i + 1. Store this in themissingvariable and break the loop. - Return
[duplicate, missing].
Walkthrough
We perform two passes over the array. In the first pass, we iterate through each number num in nums. For each num, we find its corresponding index index = abs(num) - 1. If the value at nums[index] is already negative, we know that we've encountered abs(num) before, so it must be the duplicate. If nums[index] is positive, we flip its sign to negative to mark abs(num) as seen.
After this first pass, exactly one number from 1 to n will not have been used to negate an index: the missing number. Therefore, in a second pass, we iterate from i = 0 to n-1. The index i for which nums[i] is still positive tells us that the number i+1 was the one that was missing from the set.
class Solution { public int[] findErrorNums(int[] nums) { int duplicate = -1; int missing = -1; for (int num : nums) { int index = Math.abs(num) - 1; if (nums[index] < 0) { duplicate = Math.abs(num); } else { nums[index] *= -1; } } for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { missing = i + 1; break; } } return new int[]{duplicate, missing}; }}Complexity
Time
O(n), as we perform two separate, non-nested passes over the array.
Space
O(1), as we modify the array in-place and use only a few extra variables for the results.
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal space complexity of O(1).
It's an in-place algorithm.
Cons
This approach modifies the input array. If the input must be preserved, a copy must be made first, which would negate the O(1) space advantage.
This elegant approach leverages mathematical formulas to find the duplicate and missing numbers in linear time and constant space, without modifying the input array. It's based on comparing the sum and the sum of squares of the expected set (1..n) with the actual set nums.
Algorithm
- Get the size of the array,
n. - Calculate the expected sum of numbers from 1 to
n:expectedSum = n * (n + 1) / 2. - Calculate the expected sum of squares from 1 to
n:expectedSumSq = n * (n + 1) * (2n + 1) / 6. - Initialize
actualSum = 0andactualSumSq = 0. - Iterate through the
numsarray, calculating the actual sum and sum of squares of its elements. - Find the difference between actual and expected sums:
sumDiff = actualSum - expectedSum. This equalsduplicate - missing. - Find the difference between actual and expected sums of squares:
sumSqDiff = actualSumSq - expectedSumSq. This equalsduplicate^2 - missing^2. - Calculate
sumXY = sumSqDiff / sumDiff. This equalsduplicate + missing. - Solve the two simultaneous equations:
duplicate = (sumXY + sumDiff) / 2missing = (sumXY - sumDiff) / 2
- Return
[duplicate, missing].
Walkthrough
Let the duplicate number be x and the missing number be y. We can establish two independent equations involving x and y.
- Sum Difference: The sum of the numbers in
numswill be(Sum of 1..n) - y + x. Therefore,(Sum of nums) - (Sum of 1..n) = x - y. - Sum of Squares Difference: Similarly, the sum of the squares of numbers in
numswill be(Sum of squares of 1..n) - y^2 + x^2. Therefore,(Sum of squares of nums) - (Sum of squares of 1..n) = x^2 - y^2.
We know that x^2 - y^2 = (x - y)(x + y). We can find (x - y) from the first equation, which allows us to solve for (x + y). Now we have a simple system of two linear equations:
x - y = Ax + y = B
Solving this system gives us x = (A+B)/2 and y = (B-A)/2. It's crucial to use 64-bit integers (long) for the sum calculations to prevent overflow, as n can be up to 10,000.
class Solution { public int[] findErrorNums(int[] nums) { int n = nums.length; long n_long = n; long expectedSum = n_long * (n_long + 1) / 2; long expectedSumSq = n_long * (n_long + 1) * (2 * n_long + 1) / 6; long actualSum = 0; long actualSumSq = 0; for (int num : nums) { actualSum += num; actualSumSq += (long)num * num; } long sumDiff = actualSum - expectedSum; // duplicate - missing long sumSqDiff = actualSumSq - expectedSumSq; // duplicate^2 - missing^2 long sumXY = sumSqDiff / sumDiff; // duplicate + missing int duplicate = (int)((sumXY + sumDiff) / 2); int missing = (int)((sumXY - sumDiff) / 2); return new int[]{duplicate, missing}; }}Complexity
Time
O(n), as it involves a single pass through the array to compute the sums.
Space
O(1), as it only requires a few variables to store the calculated sums.
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal space complexity of O(1).
Does not modify the input array, making it a pure function.
Cons
The sum of squares can become very large, potentially causing integer overflow if not handled with 64-bit integers (long in Java).
The logic is less direct compared to other methods.
Solutions
Solution
class Solution {public int[] findErrorNums(int[] nums) { int n = nums.length; int xs = 0; for (int i = 1; i <= n; ++i) { xs ^= i ^ nums[i - 1]; } int lb = xs & -xs; int a = 0; for (int i = 1; i <= n; ++i) { if ((i & lb) > 0) { a ^= i; } if ((nums[i - 1] & lb) > 0) { a ^= nums[i - 1]; } } int b = xs ^ a; for (int i = 0; i < n; ++i) { if (nums[i] == a) { return new int[]{a, b}; } } return new int[]{b, a}; }}class Solution {public: vector<int> findErrorNums(vector<int> &nums) { int n = nums.size(); int xs = 0; for (int i = 1; i <= n; ++i) { xs ^= i ^ nums[i - 1]; } int lb = xs & -xs; int a = 0; for (int i = 1; i <= n; ++i) { if (i & lb) { a ^= i; } if (nums[i - 1] & lb) { a ^= nums[i - 1]; } } int b = xs ^ a; for (int i = 0; i < n; ++i) { if (nums[i] == a) { return {a, b}; } } return {b, a}; }};class Solution: def findErrorNums(self, nums: List[int]) -> List[int]: xs = 0 for i, x in enumerate(nums, 1): xs ^= i ^ x a = 0 lb = xs & - xs for i, x in enumerate(nums, 1): if i & lb: a ^= i if x & lb: a ^= x b = xs ^ a for x in nums: if x == a: return [a, b] return [b, a]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.