We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Set Mismatch

Number: 645

Difficulty: Easy

Paid? No

Companies: Microsoft, Meta, Amazon, Google, Apple

Problem Description

Given an array nums containing n integers where nums is supposed to contain every number from 1 to n exactly once, one of the numbers is duplicated and one is missing. The task is to find and return the duplicate number along with the missing number.

Key Insights

  • The array is of length n and is intended to contain numbers from 1 to n.
  • One number appears twice while another number is missing entirely.
  • A simple way is to use a frequency count (often implemented via an array or hash table) to detect the duplicate.
  • Alternatively, arithmetic properties (sum and sum of squares) or XOR can be exploited to solve the problem, but using a hash table is straightforward for an easy constraint.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n) (due to using an extra data structure for frequency count)

Solution

We leverage a hash table (or an auxiliary array) to count the occurrences of each number in the array. As we iterate through the array, we detect the number that occurs twice. Then, by iterating through the numbers from 1 to n, we can determine which number is missing since it will have a count of 0.

Algorithm:

  1. Initialize an empty hash table (or an auxiliary list) to keep track of counts.
  2. Iterate through nums and update the count of each number.
  3. While updating counts, identify the number that appears twice.
  4. Iterate from 1 through n to find the missing number (the one with 0 count).
  5. Return the duplicate and missing numbers as an array.

Code Solutions

# Python solution with clear line-by-line comments.
class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        # initialize a list to count frequency; size n+1 for 1-indexing
        n = len(nums)
        count = [0] * (n + 1)
        
        duplicate = -1
        missing = -1
        
        # count frequency for each number in the array
        for num in nums:
            count[num] += 1
            # if count goes to 2, it's the duplicate
            if count[num] == 2:
                duplicate = num
        
        # check for the missing number in range 1 to n
        for i in range(1, n + 1):
            if count[i] == 0:
                missing = i
                break
        
        # return the duplicate and missing numbers as required
        return [duplicate, missing]
← Back to All Questions