A2oz

How Many Ways to Find the Duplicate Elements in an Array?

Published in Data Structures and Algorithms 2 mins read

There are several ways to find duplicate elements in an array. Here are a few common approaches:

1. Using a Hash Table (Dictionary)

  • Concept: Create a hash table (dictionary in Python) to store the frequency of each element in the array. If an element's count exceeds 1, it's a duplicate.

  • Example (Python):

    def find_duplicates(arr):
    counts = {}
    duplicates = []
    for num in arr:
        if num in counts:
            counts[num] += 1
        else:
            counts[num] = 1
    for num, count in counts.items():
        if count > 1:
            duplicates.append(num)
    return duplicates

arr = [1, 2, 3, 4, 2, 5, 6, 1]
print(find_duplicates(arr))  # Output: [1, 2]

2. Sorting and Comparison

  • Concept: Sort the array. Iterate through the sorted array, comparing adjacent elements. If they are the same, it's a duplicate.

  • Example (Python):

    def find_duplicates(arr):
    arr.sort()
    duplicates = []
    for i in range(1, len(arr)):
        if arr[i] == arr[i-1]:
            duplicates.append(arr[i])
    return duplicates

arr = [1, 2, 3, 4, 2, 5, 6, 1]
print(find_duplicates(arr))  # Output: [1, 2]

3. Using Sets

  • Concept: Create a set from the array. Sets store only unique elements. Compare the length of the set with the original array. If they differ, duplicates exist.

  • Example (Python):

    def find_duplicates(arr):
    duplicates = []
    for num in arr:
        if arr.count(num) > 1:
            duplicates.append(num)
    return duplicates

arr = [1, 2, 3, 4, 2, 5, 6, 1]
print(find_duplicates(arr))  # Output: [1, 2]

4. Using a Counter (Collections Module)

  • Concept: Utilize the Counter class from the collections module to efficiently count the occurrences of each element.

  • Example (Python):

    from collections import Counter

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

arr = [1, 2, 3, 4, 2, 5, 6, 1]
print(find_duplicates(arr))  # Output: [1, 2]

These are just a few common methods for finding duplicate elements in an array. The choice of method depends on factors like the size of the array, the frequency of duplicates, and the desired performance characteristics.

Related Articles