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
numswith lengthn.
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
- Initialization: Create an empty list
resultto store the duplicate and missing numbers. - 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.
- 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.