645. Set Mismatch - Explanation

1. Brute Force

Intuition

The array should contain each number from 1 to n exactly once, but one number is duplicated and one is missing. The most direct approach is to count how many times each number from 1 to n appears in the array. A number appearing twice is the duplicate, and a number appearing zero times is the missing one.

Algorithm

Initialize a result array to store [duplicate, missing].
For each number i from 1 to n:
- Count how many times i appears in the array.
- If the count is 0, i is the missing number.
- If the count is 2, i is the duplicate number.
Return the result.

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        res = [0, 0]
        n = len(nums)

        for i in range(1, n + 1):
            cnt = 0
            for num in nums:
                if num == i:
                    cnt += 1

            if cnt == 0:
                res[1] = i
            elif cnt == 2:
                res[0] = i

        return res

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$

2. Sorting

Intuition

After sorting, consecutive elements should differ by exactly 1. If two adjacent elements are equal, we found the duplicate. If two adjacent elements differ by 2, the missing number lies between them. We also need to handle the edge case where the missing number is n (the last element after sorting is not n).

Algorithm

Sort the array.
Initialize the result with missing = 1 (handles the case where 1 is missing).
Iterate through adjacent pairs:
- If two elements are equal, record the duplicate.
- If two elements differ by 2, the missing number is in between.
If the last element is not n, then n is the missing number.
Return [duplicate, missing].

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        res = [0, 1]
        nums.sort()

        for i in range(1, len(nums)):
            if nums[i] == nums[i - 1]:
                res[0] = nums[i]
            elif nums[i] - nums[i - 1] == 2:
                res[1] = nums[i] - 1

        if nums[-1] != len(nums):
            res[1] = len(nums)
        return res

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

3. Frequency Count (Hash Table)

Intuition

Using extra space, we can count occurrences in a single pass and then check each number's frequency. A frequency array of size n+1 lets us directly index by number value. The number with count 2 is the duplicate, and the number with count 0 is the missing one.

Algorithm

Create a count array of size n+1 initialized to 0.
Iterate through the input array and increment count for each number.
Iterate through numbers 1 to n:
- If count[i] is 0, i is the missing number.
- If count[i] is 2, i is the duplicate number.
Return [duplicate, missing].

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        res = [0, 0] # [duplicate, missing]
        count = Counter(nums)

        for i in range(1, len(nums) + 1):
            if count[i] == 0:
                res[1] = i
            if count[i] == 2:
                res[0] = i

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Negative Marking

Intuition

We can use the input array itself as a hash table by marking visited indices. For each number, we negate the value at the corresponding index. If we try to negate an already negative value, we found the duplicate. After processing, any positive value indicates its index corresponds to the missing number.

Algorithm

Iterate through the array:
- For each value, take its absolute value to get the index.
- If the value at that index is already negative, this is the duplicate.
- Otherwise, negate the value at that index.
Iterate through the array again:
- Find the index with a positive value that is not the duplicate.
- This index + 1 is the missing number.
Return [duplicate, missing].

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        res = [0, 0]

        for num in nums:
            num = abs(num)
            nums[num - 1] *= -1
            if nums[num - 1] > 0:
                res[0] = num

        for i, num in enumerate(nums):
            if num > 0 and i + 1 != res[0]:
                res[1] = i + 1
                return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

5. Math

Intuition

Using sum formulas, we can set up equations to solve for the duplicate and missing numbers. Let the duplicate be d and the missing be m. The difference between actual sum and expected sum gives us d - m. The difference between actual sum of squares and expected sum of squares gives us d^2 - m^2 = (d+m)(d-m). With these two equations, we can solve for both values.

Algorithm

Compute x = sum(nums) - sum(1 to n), which equals duplicate - missing.
Compute y = sum(nums^2) - sum(1^2 to n^2), which equals duplicate^2 - missing^2.
Since y = (duplicate + missing) * x, we get duplicate + missing = y / x.
Solve for missing: missing = (y/x - x) / 2 and duplicate = missing + x.
Return [duplicate, missing].

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        N = len(nums)
        x = 0 # duplicate - missing
        y = 0 # duplicate^2 - missing^2

        for i in range(1, N + 1):
            x += nums[i - 1] - i
            y += nums[i - 1]**2 - i**2

        missing = (y - x**2) // (2 * x)
        duplicate = missing + x
        return [duplicate, missing]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

6. Bitwise XOR

Intuition

XOR has the property that a ^ a = 0. If we XOR all numbers in the array with all numbers from 1 to n, pairs cancel out, leaving us with duplicate ^ missing. To separate them, we find a bit where they differ (using the rightmost set bit), then partition all numbers into two groups based on that bit. XORing within each group isolates the duplicate and missing values.

Algorithm

XOR all array elements with all numbers 1 to n. This gives duplicate ^ missing.
Find the rightmost set bit in the XOR result (this bit differs between duplicate and missing).
Partition all numbers (from array and from 1 to n) into two groups based on this bit.
XOR numbers within each group separately to get two candidates x and y.
Check which candidate appears in the array to identify the duplicate.
Return [duplicate, missing].

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        N = len(nums)
        # a ^ a = 0
        # xorr = (1 ^ 2 ^ ... N) ^ (nums[0] ^ nums[1] ^ ... nums[N - 1])
        # xorr = missing ^ duplicate
        xorr = 0
        for i in range(1, N + 1):
            xorr ^= i
            xorr ^= nums[i - 1]

        # bit that is set in only one number among (duplicate, missing),
        # will be set in (duplicate ^ missing)
        # take rightMost set bit for simplicity
        rightMostBit = xorr & ~(xorr - 1)

        # divide numbers (from nums, from [1, N]) into two sets w.r.t the rightMostBit
        # xorr the numbers of these sets independently
        x = y = 0
        for i in range(1, N + 1):
            if i & rightMostBit:
                x ^= i
            else:
                y ^= i

            if nums[i - 1] & rightMostBit:
                x ^= nums[i - 1]
            else:
                y ^= nums[i - 1]

        # identify the duplicate number from x and y
        for num in nums:
            if num == x:
                return [x, y]
        return [y, x]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Confusing the Output Order

The problem asks to return [duplicate, missing] in that specific order. Accidentally swapping the order and returning [missing, duplicate] produces wrong answers even when both numbers are correctly identified.

Not Handling Edge Cases at Array Boundaries

When using the sorting approach, special handling is needed if the missing number is 1 (the first element) or n (the last element). These boundary cases require explicit checks beyond just comparing adjacent elements.