💬 Discord
Sign In
NeetCode #81LC-645EasyArrays & Hashing
← Back to All Problems

#81 · #645 · Set Mismatch(错误的集合)

📌 Problem Statement & Constraints

You have a set of integers 1..n stored in an array nums of length n, but one number is duplicated and another is missing. Return [duplicate, missing]. Constraints: 2 <= nums.length <= 10^4, 1 <= nums[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. Find the duplicate with a hash set in one pass.
  2. The missing value then follows from the sum identity: sum(nums) - n(n+1)/2 = duplicate - missing.
  3. So missing = duplicate - (sum(nums) - expected_sum).
  4. This needs only O(n) time and one extra set -- no sum-of-squares, which avoids large numbers.

💻 Benchmark Python3 Implementation

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        seen = set()
        dup = -1
        for x in nums:
            if x in seen:
                dup = x
            seen.add(x)
        expected = n * (n + 1) // 2
        missing = dup - (sum(nums) - expected)
        return [dup, missing]


# O(1) space variant: negate to mark, then read the marks
class Solution2:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        dup = -1
        for x in nums:
            idx = abs(x) - 1
            if nums[idx] < 0:
                dup = abs(x)          # seen twice
            else:
                nums[idx] = -nums[idx]
        missing = -1
        for i in range(n):
            if nums[i] > 0:           # never marked -> i+1 missing
                missing = i + 1
        return [dup, missing]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one or two passes.
💾 Space Complexity
O(n) for the set-based version; O(1) auxiliary for the negation variant.

⚠️ Interview Pitfalls & Follow-ups

  • Sign error in the missing formula: sum(nums) - expected == dup - missing, so missing = dup - (sum(nums) - expected). Rearrange carefully.
  • Returning [missing, dup]: the required order is [duplicate, missing].
  • Forgetting abs in the negation variant: nums[i] may already be negative, producing a negative index.
  • Using sum-of-squares in a fixed-width language: n^4-scale values overflow 32-bit ints. Python is safe, but the set-based approach is simpler.