645. Set Mismatch

Set Mismatch

Problem Description

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  s got duplicated to another number in the set, which results in the repetition of one number and the 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 <= 104
• 1 <= nums[i] <= 104

Approach) Brute Force

The most naive solution is to consider each number from $1$ to $n$ and traverse over the whole $nums$ array to check if the current number occurs twice in $nums$ or doesn't occur at all. We need to set the duplicate number, $dup$ and the missing number, $missing$, appropriately in such cases respectively.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
    let dup = -1, missing = -1;
    for (let i = 1; i <= nums.length; i++) {
        let count = 0;
        for (let j = 0; j < nums.length; j++) {
            if (nums[j] == i)
                count++;
        }
        if (count == 2)
            dup = i;
        else if (count == 0)
            missing = i;
    }
    return [dup, missing];
};

Complexity Analysis

Time complexity:
O(n^2). We traverse over the nums-nums array of size nn for each of the numbers from 11 to nn.

Space complexity: O(1). Constant extra space is used.

Approach) Better Brute Force

In the last approach, we continued the search process, even when we'd already found the duplicate and the missing number. But, as per the problem statement, we know that only one number will be repeated and only one number will be missing. Thus, we can optimize the last approach to some extent, by stopping the search process as soon as we find these two required numbers.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
    let dup = -1, missing = -1;;
    for (let i = 1; i <= nums.length; i++) {
        let count = 0;
        for (let j = 0; j < nums.length; j++) {
            if (nums[j] == i)
                count++;
        }
        if (count == 2)
            dup = i;
        else if (count == 0)
            missing = i;
        if (dup > 0 && missing > 0)
            break;
    }
    return [dup, missing];
};

Complexity Analysis

Time complexity:
O(n^2). We traverse over the nums-nums array of size nn for each of the numbers from 11 to nn, in the worst case.

Space complexity: O(1). Constant extra space is used.

Approach) Sorting

One way to further optimize the last approach is to sort the given $nums$ array. This way, the numbers which are equal will always lie together. Further, we can easily identify the missing number by checking if every two consecutive elements in the sorted $nums$ array are just one count apart or not.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
    nums =  nums.sort(function(a,b) {return a-b});
    let dup = -1, missing = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i - 1])
            dup = nums[i];
        else if (nums[i] > nums[i - 1] + 1)
            missing = nums[i - 1] + 1;
    }
    return [dup, nums[nums.length - 1] != nums.length ? nums.length : missing];
};

Complexity Analysis

Time complexity: O(nlogn). Sorting takes O(nlogn) time.
Space complexity: O(logn). Sorting takes O(logn) space.

Approach) Using Map

The given problem can also be solved easily if we can somehow keep a track of the number of times each element of the $nums$ array occurs. One way to do so is to make an entry for each element of $nums$ in a HashMap $map$. This $map$ stores the entries in the form $(num_i, count_i)$. 

Here, $num$ refers to the $i^{th}$ element in $nums$ and $count_i$ refers to the number of times this element occurs in $nums$. Whenever the same element occurs again, we can increment the count corresponding to the same.

After this, we can consider every number from $1$ to $n$, and check for its presence in $map$. If it isn't present, we can update the $missing$ variable appropriately. But, if the $count$ corresponding to the current number is $2$, we can update the $dup$ variable with the current number.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
    let n = nums.length
    const map = {}
    let dup, missing
    for (let num of nums) {
        if (!(num in map)) map[num] = 1
        else dup = num
    }
    
    for (let i = 1; i <= n; i++) {
        if (!(i in map)) missing = i
    }
    
    return [dup, missing]
};

Complexity Analysis

Time complexity: O(n). Traversing over nums-nums of size n-n takes O(n) time. Considering each number from 11 to n-n also takes O(n) time.

Space complexity: O(n). map-map can contain at most n-n entries for each of the numbers from 11 to n-n.

Approach) Native

In order to solve this problem with O(1) extra space, we can use nums directly to keep track of which numbers have been seen so far. To do so, we need to be able to modify the elements of nums in such a way as to be easily able to obtain the original value again.

One of the easiest ways to do this is with the use of the mod operator (%). Since the largest value nums[i] is 10^4, we can use that number as our base. By adding 10^4 to the value of an element, it can now tell us two things: the original value of the element (num % 10^4) and whether or not the number equal to the index has been seen (num > 10^4).

Since the values in nums are 1-indexed and nums itself is 0-indexed, however, we'll have to shift the mod function to (nums - 1) % 10^4.

If we iterate through nums and apply this addition, then at the end, we'll know that the value that was seen twice will be > 20000 and the number that was never seen is < 10001.

So we just have to iterate through nums a second time, check for these values, add them to our answer (ans), and then return ans.

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
    let N = nums.length, ans = [,]
    for (let i = 0; i < N; i++)
        nums[(nums[i] - 1) % 10000] += 10000
    for (let i = 0; i < N; i++)
        if (nums[i] > 20000) ans[0] = i + 1
        else if (nums[i] < 10001) ans[1] = i + 1
    return ans
};

Approach) XOR (Bit Manipulation)

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function(nums) {
    let n = nums.length, sumXor = 0;
    let mark = new Array(n + 1).fill(0);
    let ans = new Array(2).fill(0);

    for (let i = 0; i < n; i++) {
        sumXor ^= nums[i] ^ (i + 1);

        if (mark[nums[i]] == 1) {
            ans[0] = nums[i];
        }

        mark[nums[i]]++;
    }

    ans[1] = sumXor ^ ans[0];
    return ans;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem #645. Set Mismatch

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!