How to Find All Duplicates in an Array using Python?

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

Using Python’s Collections.Counter to Find All Duplicates in Array

Using collections.Counter in Python allows us to count the frequencies of the elements in an array or list in Python. Then, we can use the List comprehensions to create a list of the duplicate elements in an array by checking their frequencies. Finally, we need to convert it to set, this allows us to filter out the duplicates in the duplicates.

1
2
3
4

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        c = collections.Counter(nums)
        return set([x for x in nums if c[x] > 1])

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        c = collections.Counter(nums)
        return set([x for x in nums if c[x] > 1])

This solution requires O(N) time and O(N) space as we are storing the frequencies in a dictionary object.

–EOF (The Ultimate Computing & Technology Blog) —