Set Mismatch — Solution in Python, Java & C++
Set Mismatch solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Google.
Set Mismatch is an easy coding problem on arrays, hash table and sorting, asked in Amazon, Google and Bloomberg interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting, Bit Manipulation
- Asked at: Amazon, Google, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You have a set s that originally held the numbers 1 through n. Because of an error, one value was duplicated on top of another, so the array nums now contains one number twice and is missing one number entirely.
Return an array [duplicated, missing].
Example 1
Input: nums = [1,2,2,4]
Output: [2,3]
Explanation: 2 appears twice, and 3 never appears.
Example 2
Input: nums = [1,1]
Output: [1,2]
Example 3
Input: nums = [3,2,2]
Output: [2,1]
Constraints
2 <= nums.length <= 401 <= nums[i] <= nums.length
Hints for Set Mismatch
Hint 1
Count how often each of
1..noccurs — the answer is the value counted twice and the value counted zero times.Hint 2
A sum-based trick also works: compare the actual sum against
n(n+1)/2and the actual sum of squares against its expected value.Hint 3
The order of the returned pair matters: duplicate first, missing second.
How to solve Set Mismatch
Count how often each of 1..n appears: the duplicate is the value counted twice, the missing one the value counted zero times.
Approach
- Tally each element into
count[1..n]. - Walk
vfrom 1 ton, recording thevwith count 2 and thevwith count 0. - Return
[dup, missing].
Why it works
Exactly one value was written over another, so precisely one count is 2 and one is 0, and every other is 1.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- The order of the pair is fixed: duplicate first.
- The sum/sum-of-squares algebra is O(1) space but easy to get wrong; the counting array is the clean answer.
Reference solution
Python
def findErrorNums(nums):
n = len(nums)
count = [0] * (n + 1)
for x in nums:
count[x] += 1
dup = missing = 0
for v in range(1, n + 1):
if count[v] == 2:
dup = v
elif count[v] == 0:
missing = v
return [dup, missing]Java
public static int[] findErrorNums(int[] nums) {
int n = nums.length;
int[] count = new int[n + 1];
for (int x : nums) count[x]++;
int dup = 0, missing = 0;
for (int v = 1; v <= n; v++) {
if (count[v] == 2) dup = v;
else if (count[v] == 0) missing = v;
}
return new int[]{dup, missing};
}C++
vector<int> findErrorNums(vector<int>& nums) {
int n = (int) nums.size();
vector<int> count(n + 1, 0);
for (int x : nums) count[x]++;
int dup = 0, missing = 0;
for (int v = 1; v <= n; v++) {
if (count[v] == 2) dup = v;
else if (count[v] == 0) missing = v;
}
return {dup, missing};
}JavaScript
var findErrorNums = function(nums) {
const n = nums.length;
const count = new Array(n + 1).fill(0);
for (let i = 0; i < n; i++) count[nums[i]]++;
let dup = 0, missing = 0;
for (let v = 1; v <= n; v++) {
if (count[v] === 2) dup = v;
else if (count[v] === 0) missing = v;
}
return [dup, missing];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets