Set Mismatch

Easy
184.

Set Mismatch

Set Mismatch is an easy coding problem on arrays, hash table and sorting, asked in Amazon, Google and Bloomberg interviews.

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 <= 40
  • 1 <= nums[i] <= nums.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 40
  • 1 <= nums[i] <= nums.length

Hints for Set Mismatch

  1. Hint 1

    Count how often each of 1..n occurs — the answer is the value counted twice and the value counted zero times.

  2. Hint 2

    A sum-based trick also works: compare the actual sum against n(n+1)/2 and the actual sum of squares against its expected value.

  3. 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

  1. Tally each element into count[1..n].
  2. Walk v from 1 to n, recording the v with count 2 and the v with count 0.
  3. 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