Solution: Set Mismatch (ver. 1)

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Note: This is my first version of a solution for this problem. Though I consider this version to be a less complex solution more appropriate for an "Easy" problem, my second solution version demonstrates how to achieve the solution with a space complexity of only O(1) extra space instead of O(N).

---

Leetcode Problem #645 (Easy): Set Mismatch

---

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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.

---

Examples:

Example 1:
Input:	nums = [1,2,2,4]
Output:	[2,3]

Example 2:
Input:	nums = [1,1]
Output:	[1,2]

---

Constraints:

• 2 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^4

---

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

For this problem, we can take advantage of some math, because one thing we know about a sequence of numbers from 1 to N is that their sum should equal the Nth triangular number (N * (N + 1) / 2).

Since the only difference between the ideal array ranging from 1 to N and our input array nums is the duplicated number, that means that the difference between the sum of nums and the Nth triangular number is the same as the difference between our duplicated number (dupe) and the missing number.

We can easily find the duplicated number by utilizing a boolean array (seen) to keep track of which numbers have already been seen. While iterating through nums, whenever we come across a number for the second time, that number must be our dupe. We can also use this iteration to find the difference in the sums.

Then we can just return the dupe and the sum difference applied to the dupe to identify the missing number.

---

Implementation:

Javascript doesn't have a boolean array, so we can use the typed Uint8Array() as the closest stand-in. Python likewise doesn't have a boolean array, so we'll have to use a normal list.

---

Javascript Code:

(Jump to: Problem Description || Solution Idea)

var findErrorNums = function(nums) {
    let N = nums.length, dupe, sum = N * (N + 1) / 2,
        seen = new Uint8Array(N+1)
    for (let i = 0; i < N; i++) {
        let num = nums[i]
        sum -= num
        if (seen[num]) dupe = num
        seen[num]++
    }
    return [dupe, sum + dupe]
};

---

Python Code:

(Jump to: Problem Description || Solution Idea)

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        N, dupe = len(nums), 0
        seen, sumN = [0] * (N+1), N * (N+1) // 2
        for num in nums:
            sumN -= num
            if seen[num]: dupe = num
            seen[num] += 1
        return [dupe, sumN + dupe]

---

Java Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
    public int[] findErrorNums(int[] nums) {
        int N = nums.length, sum = N * (N + 1) / 2;
        int[] ans = new int[2];
        boolean[] seen = new boolean[N+1];
        for (int num : nums) {
            sum -= num;
            if (seen[num]) ans[0] = num;
            seen[num] = true;
        }
        ans[1] = sum + ans[0];
        return ans;
    }
}

---

C++ Code:

(Jump to: Problem Description || Solution Idea)

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int N = nums.size(), sum = N * (N + 1) / 2;
        vector<int> ans(2);
        vector<bool> seen(N+1);
        for (int num : nums) {
            sum -= num;
            if (seen[num]) ans[0] = num;
            seen[num] = true;
        }
        ans[1] = sum + ans[0];
        return ans;
    }
};