Set Mismatch Solution in Python

Problem Description

Ah, the classic “Set Mismatch” problem! It’s like that awkward moment when you realize you’ve been invited to a party, but you’re the only one who didn’t get the memo about the dress code. In this problem, you’re given an array of integers where the numbers range from 1 to n. However, one number is duplicated, and another number is missing. Your task is to find out which number is duplicated and which one is missing.

Imagine you’re at a family reunion, and everyone is supposed to bring a dish. But Aunt Edna brought her famous potato salad (again), and Cousin Jimmy forgot to bring his famous mac and cheese. Now, you have to figure out who brought what and who forgot to bring anything at all.

Code Solution

class Solution:
    def findErrorNums(self, nums: list[int]) -> list[int]:
        for num in nums:
            if nums[abs(num) - 1] < 0:
                duplicate = abs(num)
            else:
                nums[abs(num) - 1] *= -1

        for i, num in enumerate(nums):
            if num > 0:
                return [duplicate, i + 1]
    

Approach

The approach taken in this solution is quite clever. It uses the input array itself to track which numbers have been seen. By negating the value at the index corresponding to each number, we can identify duplicates when we encounter a number whose corresponding index is already negative. After that, a second pass through the array helps us find the missing number by checking which index still has a positive value.

Time and Space Complexity

Time Complexity: O(n) – We traverse the list twice, which is linear in relation to the size of the input.

Space Complexity: O(1) – We are using the input array for tracking, so no additional space is used.

Real-World Example

Think of a classroom where students are supposed to submit their assignments. Each student has a unique ID from 1 to n. However, one student (let’s say Student 3) submitted their assignment twice (because they forgot they already did it), while another student (Student 5) didn’t submit anything at all. Your job is to figure out that Student 3 is the duplicate and Student 5 is the missing one.