[How To] find all duplicates and the number of repetitions

Let’s write a function which will find all duplicate elements and the number of repetitions in the given list using python. For example, function will return {11: 3, 1024: 2} for [11, 11, 23, 11, 1024, 66, 78, 1024] list.

• Solution 1
• Solution 2
• Solution 3
• Complexity of Algorithm

Solution 1

A = [11, 11, 23, 11, 1024, 66, 78, 1024]
counter = {}

for elem in A:
    counter[elem] = counter.get(elem, 0) + 1

doubles = {element: count for element, count in counter.items() if count > 1}

print(doubles)

Solution 2

A = [11, 11, 23, 11, 1024, 66, 78, 1024]

from collections import Counter
counter = Counter(A)

Solution 3

A = [11, 11, 23, 11, 1024, 66, 78, 1024]
from collections import defaultdict
counter = defaultdict(int)
for elem in A:
    counter[elem] += 1

Complexity of Algorithm

The cost of compiling a counter list: you need to insert values into the dictionary n times. The insert consists of two operations: first, check to see if there is such a number in the dictionary and, in fact, the insert is all together O(1) average or O(n). So, the cost of compiling a counter is O(n) on average, O(n^2) at worst.

The next step is to filter only what you need. In the worst case, you need to go through the entire counter – again n operations on O(1) or in the worst O(n) – take from the dictionary, compare, write to a new dictionary. On average O(n).

Total O(n) on average or for specially prepared data O(n^2) at worst.