Check Duplicates

The problem “Checking for Duplicates” involves identifying if an array A contains any duplicate elements. This problem can be seen as a special case of checking for a common element between two arrays, but here both arrays are the same. Various approaches can solve this, such as sorting the array first, using a hash set, or a brute-force comparison.

Here’s a table illustrating the value of ( i ) and ( j ) for an array ( A = [2, 1, 3, 1] ) which has one duplicate element (1). The table goes through each combination of ( i ) and ( j ).

The algorithm would terminate at Step 5 since it finds ( A[i] = A[j] ) (1 = 1) and return true, indicating that there’s at least one duplicate element in the array.

Here’s a table showing all steps for the array ( A = [2, 1, 3, 1] ) without the check, as if we are printing each step instead of returning boolean values.

Here, all combinations of ( i ) and ( j ) are visited once. This is a full enumeration of the pairs of indices.

Brute-force - Java

In this approach, two nested loops compare each pair of elements in the array A.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

public class Main {
    public static boolean checkDuplicates(int[] A) {
        for(int i = 0; i < A.length; i++) {
            for(int j = i + 1; j < A.length; j++) {
                if(A[i] == A[j]) return true;
            }
        }
        return false;
    }
}

Brute-force - C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#include <iostream>
using namespace std;

bool checkDuplicates(int A[], int n) {
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if(A[i] == A[j]) return true;
        }
    }
    return false;
}

Brute-force - Python

1
2
3
4
5
6

def checkDuplicates(A):
    for i in range(len(A)):
        for j in range(i + 1, len(A)):
            if A[i] == A[j]:
                return True
    return False

Hash Set - Java

Using a hash set provides a more efficient solution.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import java.util.HashSet;

public class Main {
    public static boolean checkDuplicates(int[] A) {
        HashSet<Integer> set = new HashSet<>();
        for(int i : A) {
            if(set.contains(i)) return true;
            set.add(i);
        }
        return false;
    }
}

Hash Set - C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <iostream>
#include <unordered_set>
using namespace std;

bool checkDuplicates(int A[], int n) {
    unordered_set<int> set;
    for(int i = 0; i < n; i++) {
        if(set.find(A[i]) != set.end()) return true;
        set.insert(A[i]);
    }
    return false;
}

Hash Set - Python

1
2
3
4
5
6
7

def checkDuplicates(A):
    s = set()
    for i in A:
        if i in s:
            return True
        s.add(i)
    return False

By using a hash set, you eliminate the need for nested loops, and the operation becomes more efficient with a time complexity of O(n).

Key Takeaway

The outer loop index go from 0 to array length - 1. The inner loop index goes from inner i + 1 to array length. Easy to make out of bounds error when using nested loops.