Problem 645

(Last updated: )

Question statement

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number. You are given an integer array nums representing the data status of this set after the error. Find the number that occurs twice and the number that is missing and return them in the form of an array.

Solution

After trying and failing for 30 minutes to find a one-pass solution, I just went for the most straightforward hashing trick (any optimal code is going to be O(n) anyway)

Main idea:

Initialize a set unique that has values 1..n. Create a frequency counter for nums, now scan through the counter removing any element that is already in the unique set, while also checking if any frequency is equal to 2. If such an element is encountered, that’s the first part of our answer. Continue with the loop until the nums is exhausted. The value remaining in unique is the missing number, which constitutes the second part of our answer.

There is a slick way of doing a similar thing, that always seems to escape me. I need to be better with remembering this trick! Note that by design the max element of nums = len(nums) = n, and so we can create an temp array of size n+1, and go through nums, and update the frequency of nums[i] at temp[i]. Finally scan temp for the non-zero index whose frequency is zero, and the non-zero index whose frequency is 2, and return these numbers in the right order as a list.

Code:

First approach:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def findErrorNums(self, nums: List[int]) -> List[int]:
    unique = set()
    n=len(nums)
    c = Counter(nums)
    ans = [-1,-1]
    for i in range(n):
        unique.add(i+1)
    
    for item in c:
        if(c[item] == 2):
            ans[0] = item
        if(item in unique):
            unique.remove(item)
    ans[1] = list(unique)[-1]
    return ans

Slick approach:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findErrorNums(self, nums: List[int]) -> List[int]:
    n = len(nums)
    freq = [0 for _ in range(n+1)]
    ans = [-1,-1]
    for i in range(n):
        freq[nums[i]] +=1
    for i in range(len(freq)):
        if(i==0):
            continue
        if(freq[i] == 2):
            ans[0] = i
        elif(freq[i] == 0):
            ans[1] = i
    return ans

Comments:

Time complexity: O(n) for both approaches

At the time of submission, the first solution passes leetcode submission cases in 165ms, beating 69.14% of users. It uses 18.79MB of memory, beating 43.97% of users.
At the time of submission, the second solution passes leetcode submission cases in 149ms, beating 94.83% of users. It uses 17.64MB of memory, beating 98.71% of users.