Set Mismatch - Leetcode Solution

Problem:

You have an array of length n comprising unique elements that range from 1 to n. However, one of the elements in the array got replaced by another element of the array, which results in repetition of one element and loss of one element from the array. Find the repeated and the missing element.

Example:

Input: [1,2,2,4] Output: [2,3]

Explanation: The missing element in the array is 3 and the repeated element is 2.

Solution:

To solve this problem, we can use a hash table to store the frequency of each number in the array. The number that occurs twice will have a frequency of 2, and the number that is missing will have a frequency of 0.

We can iterate through the array to update the frequency of each number. Then we can iterate through the hash table to find the number with frequency 2 and the number with frequency 0.

Here is the Python code for this solution:

def findErrorNums(nums): freq = {} for num in nums: if num in freq: freq[num] += 1 else: freq[num] = 1

missing = -1
repeated = -1
for i in range(1, len(nums)+1):
    if i not in freq:
        missing = i
    elif freq[i] == 2:
        repeated = i

return [repeated, missing]

Time Complexity: The time complexity of this solution is O(n) because we loop through the array twice and the hash table once.

Space Complexity: The space complexity of this solution is also O(n) because we use a hash table to store the frequency of each number.

1