Python Program to Find Duplicate Elements in Array

You can find duplicate elements in an array in Python by using a set to track seen items and collecting duplicates with a list comprehension like duplicates = list(set([x for x in arr if arr.count(x) > 1])).

Examples

Input[1, 2, 3, 4]

Output[]

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

Output[2, 4]

Input[]

Output[]

How to Think About It

To find duplicates, look at each element and check if it appears more than once in the array. Keep track of elements you have already counted as duplicates to avoid repeats. Using a set helps remember which duplicates you found.

Algorithm

1

Get the input array.

2

Create an empty set to store duplicates.

3

For each element in the array, check if it appears more than once.

4

If yes, add it to the duplicates set.

5

Convert the set to a list and return it.

Code

python

def find_duplicates(arr):
    duplicates = set()
    seen = set()
    for item in arr:
        if item in seen:
            duplicates.add(item)
        else:
            seen.add(item)
    return list(duplicates)

# Example usage
arr = [1, 2, 2, 3, 4, 4, 4]
print(find_duplicates(arr))

Output

[2, 4]

Dry Run

Let's trace the array [1, 2, 2, 3, 4, 4, 4] through the code

1

Initialize sets

duplicates = set(), seen = set()

2

Process item 1

1 not in seen, add 1 to seen -> seen = {1}

3

Process item 2

2 not in seen, add 2 to seen -> seen = {1, 2}

4

Process item 2 again

2 in seen, add 2 to duplicates -> duplicates = {2}

5

Process item 3

3 not in seen, add 3 to seen -> seen = {1, 2, 3}

6

Process item 4

4 not in seen, add 4 to seen -> seen = {1, 2, 3, 4}

7

Process item 4 again

4 in seen, add 4 to duplicates -> duplicates = {2, 4}

8

Process item 4 again

4 in seen, add 4 to duplicates (already there) -> duplicates = {2, 4}

9

Return duplicates

Return list(duplicates) -> [2, 4]

Item	Seen Set	Duplicates Set
1	{1}	{}
2	{1, 2}	{}
2	{1, 2}	{2}
3	{1, 2, 3}	{2}
4	{1, 2, 3, 4}	{2}
4	{1, 2, 3, 4}	{2, 4}
4	{1, 2, 3, 4}	{2, 4}

Why This Works

Step 1: Track seen elements

We use a set called seen to remember elements we have already checked.

Step 2: Identify duplicates

If an element is already in seen, it means it appeared before, so we add it to duplicates.

Step 3: Return duplicates list

Finally, we convert the duplicates set to a list to return all duplicate elements found.

Alternative Approaches

Using list count method

python

def find_duplicates(arr):
    return list(set([x for x in arr if arr.count(x) > 1]))

print(find_duplicates([1, 2, 2, 3, 4, 4, 4]))

Simple but inefficient for large arrays because <code>count</code> scans the list each time.

Using collections.Counter

python

from collections import Counter

def find_duplicates(arr):
    counts = Counter(arr)
    return [item for item, count in counts.items() if count > 1]

print(find_duplicates([1, 2, 2, 3, 4, 4, 4]))

Efficient and clean, uses built-in counting to find duplicates.

Complexity: O(n) time, O(n) space

Time Complexity

The program loops through the array once, so it runs in linear time O(n). Checking and adding to sets is O(1) on average.

Space Complexity

Extra space is used for two sets to store seen elements and duplicates, so space is O(n) in the worst case.

Which Approach is Fastest?

Using sets to track seen elements is faster than counting each element multiple times. The Counter method is also efficient and clean.

Approach	Time	Space	Best For
Set tracking	O(n)	O(n)	Large arrays, efficient
List count method	O(n²)	O(n)	Small arrays, simple code
collections.Counter	O(n)	O(n)	Clean code, built-in support