LeetCode 645: Set Mismatch Solution in Python – A Step-by-Step Guide

What Is LeetCode 645: Set Mismatch?

In LeetCode 645: Set Mismatch, you’re given an integer array nums of length n containing numbers from 1 to n, where one number is duplicated and one is missing. Your task is to return a list [duplicate, missing] identifying both. For example, with nums = [1, 2, 2, 4], the duplicate is 2 (appears twice), and the missing number is 3 (not present). The array has exactly one duplicate and one missing number, and we need to find them efficiently. This problem tests your ability to detect anomalies in a constrained set of integers.

Problem Statement

• Input:
• nums: List of integers, length n, containing 1 to n with one duplicate and one missing.
• Output: A list [duplicate, missing] of two integers.
• Rules:
• Numbers range from 1 to n.
• Exactly one number appears twice, one is absent.
• Return [duplicate, missing].

Constraints

• 2 ≤ nums.length ≤ 10⁴.
• 1 ≤ nums[i] ≤ 10⁴.

Examples

• Input: nums = [1, 2, 2, 4]
• Output: [2, 3] (Duplicate 2, missing 3)
• Input: nums = [3, 2, 3, 1]
• Output: [3, 4] (Duplicate 3, missing 4)
• Input: nums = [1, 1]
• Output: [1, 2] (Duplicate 1, missing 2)

These examples set the shelf—let’s solve it!

Understanding the Problem: Finding the Mismatch

To solve LeetCode 645: Set Mismatch in Python, we need to identify the duplicate and missing number in an array of length n containing numbers 1 to n with one duplication and one omission. A brute-force approach—counting occurrences of each number—would be O(n) with O(n) space, reasonable but not optimal. Since the numbers align with indices (1 to n), we can optimize by marking or using math. We’ll explore:

• Best Solution (In-Place Marking with Array Indices): O(n) time, O(1) space—fast and space-efficient.
• Alternative Solution (Hash Set Approach): O(n) time, O(n) space—simple but uses extra memory.

Let’s start with the in-place marking solution, breaking it down for beginners.

Best Solution: In-Place Marking with Array Indices

Why This Is the Best Solution

The in-place marking approach is the top choice for LeetCode 645 because it’s efficient—O(n) time with O(1) space—and cleverly uses the array itself as a marker by negating values at indices corresponding to seen numbers, avoiding extra data structures. It fits constraints (n ≤ 10⁴) perfectly and is elegant once you grasp the index trick. It’s like flipping a book’s page to mark it as checked out!

How It Works

Think of this as a shelf marker:

• Step 1: Mark Seen Numbers:
• For each num, use its value (minus 1) as an index.
• Negate the number at that index if positive.
• If already negative, num is the duplicate.
• Step 2: Find Missing Number:
• Scan array again; the index of the first positive number (plus 1) is missing.
• Step 3: Return Result:
• Return [duplicate, missing].

It’s like a sign flipper—mark and spot!

Step-by-Step Example

Example: nums = [1, 2, 2, 4]

• Step 1: Mark:
• num = 1: Index 0 (1-1), nums[0] = 1 → -1, nums = [-1, 2, 2, 4].
• num = 2: Index 1, nums[1] = 2 → -2, nums = [-1, -2, 2, 4].
• num = 2: Index 1, nums[1] = -2 (already negative), duplicate = 2.
• num = 4: Index 3, nums[3] = 4 → -4, nums = [-1, -2, 2, -4].
• Step 2: Find missing:
• nums = [-1, -2, 2, -4], index 2 is positive, missing = 2 + 1 = 3.
• Step 3: Return [2, 3].
• Output: [2, 3].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        # Step 1: Mark seen numbers and find duplicate
        duplicate = 0
        for num in nums:
            idx = abs(num) - 1  # Convert to 0-based index
            if nums[idx] > 0:
                nums[idx] = -nums[idx]  # Mark as seen
            else:
                duplicate = abs(num)  # Already marked, this is duplicate

        # Step 2: Find missing number
        missing = 0
        for i in range(len(nums)):
            if nums[i] > 0:
                missing = i + 1  # Positive index + 1 is missing
                break

        # Step 3: Return result
        return [duplicate, missing]

• Line 4: Init duplicate tracker.
• Lines 5-11: Mark:
• Use abs(num) - 1 as index, negate if positive, set duplicate if already negative.
• Lines 14-18: Find missing:
• First positive number’s index + 1 is missing.
• Time Complexity: O(n)—two passes.
• Space Complexity: O(1)—in-place.

This is like a number flipper—mark and find!

Alternative Solution: Hash Set Approach

Why an Alternative Approach?

The hash set approach tracks seen numbers in a set—O(n) time, O(n) space. It’s simpler, explicitly identifying the duplicate and using sum differences to find the missing number, but requires extra memory. It’s like keeping a checklist of books you’ve seen!

How It Works

Picture this as a number checker:

• Step 1: Build set, find duplicate.
• Step 2: Compute expected sum (1 to n), actual sum.
• Step 3: Missing = expected - actual + duplicate.
• Step 4: Return [duplicate, missing].

It’s like a sum balancer—check and subtract!

Step-by-Step Example

Example: Same as above

• Step 1: Set = {1, 2}, duplicate = 2 (seen twice).
• Step 2:
• Expected sum = (4 * 5) / 2 = 10 (1 to 4).
• Actual sum = 1 + 2 + 2 + 4 = 9.
• Step 3: Missing = 10 - 9 + 2 = 3.
• Step 4: Return [2, 3].
• Output: [2, 3].

Code for Hash Set Approach

Copy codeclass Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        # Step 1: Find duplicate using set
        seen = set()
        duplicate = 0
        for num in nums:
            if num in seen:
                duplicate = num
            seen.add(num)

        # Step 2: Compute sums
        n = len(nums)
        expected_sum = (n * (n + 1)) // 2
        actual_sum = sum(nums)

        # Step 3: Find missing
        missing = expected_sum - actual_sum + duplicate

        # Step 4: Return result
        return [duplicate, missing]

• Lines 4-9: Build set, find duplicate.
• Lines 12-14: Compute expected and actual sums.
• Line 17: Calculate missing number.
• Time Complexity: O(n)—single pass and sum.
• Space Complexity: O(n)—hash set.

It’s a set checker—simple but bulkier!

Comparing the Two Solutions

• In-Place Marking (Best):
• Pros: O(n) time, O(1) space, no extra memory.
• Cons: Modifies input array.
• Hash Set (Alternative):
• Pros: O(n) time, O(n) space, preserves input.
• Cons: Extra space.

In-place wins for efficiency.

Additional Examples and Edge Cases

• Input: [2, 2]
• Output: [2, 1].
• Input: [1, 5, 3, 2, 2]
• Output: [2, 4].

Both handle these well.

Complexity Breakdown

• In-Place: Time O(n), Space O(1).
• Hash Set: Time O(n), Space O(n).

In-place is optimal.

Key Takeaways

• In-Place: Index magic—smart!
• Hash Set: Set simplicity—clear!
• Mismatch: Finding errors is fun.
• Python Tip: Loops rock—see Python Basics.

Final Thoughts: Fix That Shelf

LeetCode 645: Set Mismatch in Python is a neat array puzzle. In-place marking offers speed and minimalism, while hash set provides a clear alternative. Want more? Try LeetCode 287: Find the Duplicate Number or LeetCode 448: Find All Numbers Disappeared in an Array. Ready to sort? Head to Solve LeetCode 645 on LeetCode and find that mismatch today!