Efficient Methods to Identify Duplicates in a 1 to 100 Array

Identifying duplicates within an array, specifically one that contains numbers from 1 to 100, can be efficiently accomplished using various programming techniques. This article explores two effective methods: one using sets and another leveraging an array-based mapping approach. Both methods are optimized for performance and space efficiency.

Method 1: Set-Based Approach

One efficient way to identify duplicates is to use a set to track seen numbers. This method involves iterating through the array and checking if each number has already been encountered. Here’s a Python implementation:

def find_duplicates(arr):
    seen  set()
    duplicates  set()
    for num in arr:
        if num in seen:
            (num)
        else:
            (num)
    return list(duplicates)

Example Usage:

array  [1, 2, 3, 4, 5, 1, 2, 6, 7, 8, 9, 10, 10]
print(find_duplicates(array))

Explanation:
Set for Seen Numbers: Maintain a set called seen to store the numbers encountered so far.

Set for Duplicates: Maintain a set called duplicates to store numbers that appear more than once.

Loop Through Array: For each number in the input array:

If the number is already in seen, add it to duplicates. Otherwise, add it to seen.

Return Duplicates: Convert the duplicates set to a list and return it.

This approach operates in O(n) time complexity and uses O(n) space complexity, making it efficient for the given problem.

Method 2: Array-Based Mapping Approach

Another efficient method is to use an array-based mapping approach. Given that the array contains numbers from 1 to 100, an array of size 101 can be used to track the occurrence of each number. Here’s a detailed explanation:

Create a mapping array of 101 elements (102nd element is unused). Iterate through the given array one element at a time. For each element x: If map[x] 0, set map[x] 1, indicating the first occurrence of the number. If map[x] 1, set map[x] 2, indicating a duplicate. The elements with map[x] 1 are unique and non-repeated.

Example Implementation:

def find_duplicates(arr):
    map  [0] * 101
    duplicates  []
    for num in arr:
        if map[num]  0:
            map[num]  1
        elif map[num]  1:
            (num)
            map[num]  2
    return duplicates

Time Complexity: O(n) - You scan the array once.

Space Complexity: O(1) - You only store an array of constant size (100 elements).

Conclusion

Both the set-based and array-based mapping approaches are efficient for identifying duplicates in an array containing numbers from 1 to 100. The set-based approach is straightforward and easy to implement, while the array-based mapping approach is more compact and utilizes less space. The choice of method depends on the specific requirements and constraints of the problem at hand.