Domain 1EasyCORE

Set Mismatch

The problem involves identifying two numbers in an array: one that appears twice (a duplicate) and another that is missing from the set of integers from 1 to n. The input is an integer array `nums` where each element is between 1 and n, inclusive. The output should be a list containing the duplicate number followed by the missing number.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#Math

645. Set Mismatch

Model: qwen2.5-coder:14b
Topics: Hash Table,Math
FAANG asked: 1
Acceptance rate: 41.1%


Problem Breakdown

The problem involves identifying two numbers in an array: one that appears twice (a duplicate) and another that is missing from the set of integers from 1 to n. The input is an integer array nums where each element is between 1 and n, inclusive. The output should be a list containing the duplicate number followed by the missing number.

Inputs:

  • An integer array nums with length n.

Outputs:

  • A list of two integers: [duplicate, missing].

Implicit Constraints:

  • The array contains exactly one duplicate and one missing number.
  • The numbers in the array are within the range [1, n].

Intuition

A brute-force approach would involve using nested loops to check for duplicates and then iterating through the expected set of numbers from 1 to n to find the missing number. This approach has a time complexity of O(n^2) and is inefficient given the constraints.

A more efficient approach leverages the properties of the array and the range of numbers. By marking visited elements in place, we can identify the duplicate and missing numbers with a single pass through the array, achieving linear time complexity.

Approach

  1. Initialization: Create an empty list result to store the duplicate and missing numbers.
  2. Identify Duplicate: Iterate through the array. For each number, use its absolute value as an index (subtract 1) and mark the corresponding element in the array as negative. If a number is already marked negative, it indicates that the number has been seen before, hence it’s the duplicate.
  3. Identify Missing Number: After marking all numbers, iterate through the array again. The index of the first positive number (plus 1) is the missing number since it was never visited.

Complexity Analysis

  • Time Complexity: O(n). We make two passes over the array, each taking linear time.
  • Space Complexity: O(1). We use only a constant amount of extra space for variables and do not modify the input array in place.

Solution

def findErrorNums(nums):
    result = [0, 0]
    
    # Step 1: Identify the duplicate number
    for num in nums:
        index = abs(num) - 1
        if nums[index] < 0:
            result[0] = index + 1  # Duplicate number
        else:
            nums[index] *= -1
    
    # Step 2: Identify the missing number
    for i in range(len(nums)):
        if nums[i] > 0:
            result[1] = i + 1  # Missing number
            break
    
    return result

Edge Cases Handled

  • Single Element Array: The problem constraints ensure that the array has at least two elements, so this case is not applicable.
  • All Elements Unique Except One Duplicate: The algorithm correctly identifies the duplicate and missing numbers even if all other numbers are unique except for one duplicate.
  • Duplicate is Also Missing: If the duplicate number happens to be the missing number (e.g., [1, 2, 2]), the algorithm still correctly identifies it as both the duplicate and missing number.