Contains Duplicate

We are given an array and it may be containing duplicates elements or maybe not. So we need to check if it contains duplicate.

Examples

[1, 3, 5, 1]

true

[“apple”, “mango”, “orange”, “mango”]

true

[22.0, 4.5, 3.98, 45.6, 13.54]

false

Approach

We can check an array in several ways to check whether it contains duplicates or not. The most common method is the “Brute Force method”. But it has a time complexity of O(n²) and it is good for academic purposes only. But we another to solve our problem in less time complexity “Hash set method” or “Hash table method” this method is much more efficient than the “Brute Force method”. The Hash Set method takes the time complexity of O(n).

Hash set method

This method is even simpler and efficient than others. All we need to know that set does not contain duplicates. That means if we try to add a duplicate value is set it will give an error. If we use this method all we have to do is just loop over array elements, insert them into the hash set. Then compare the size of the set to the array. If it is not equal to set then the array contains duplicates else not.

Algorithm

1. First, we create a function that takes an array as an argument.
2. After that, in our function, we create a set that contains all the value of an array.
3. Set does not allow the duplicates, that means if the array contains duplicates then its size will be different than the size of the set.
4. Finally, we compare the size of both array and set. If there is a difference in their size then the array contains duplicates else all elements are distinct.

Explanation

In our program we use hash set to check the duplicates First, we will make a function to check. In which we will make a hash set and give it all the values of the array. After that set removes the duplicates if it contains any and its size will be different in comparison to the array else it will not affect the size of the set.

C++ code to check if array contains duplicates

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

bool contain_duplicate(int arr[], int n)
{
    unordered_set<int> myset;
    bool flag = 0;

    for (int i = 0; i < n; i++)
    {
        if (myset.find(arr[i]) == myset.end())
            myset.insert(arr[i]);

        else
        {
            flag = 1;
            break;
        }

    }
    return flag;
}
int main()
{
    int arr[] = {1, 5, 2, 4, 3, 7, 8, 9, 1};
    int n = sizeof(arr) / sizeof(int);

    cout<< boolalpha <<contain_duplicate(arr, n);
    return 0;
}

true

Java code to check if array contains duplicates

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class contain_duplicate
{

    public static boolean solution(Integer [] array)
    {

        Set<Integer> myset = new HashSet<> (Arrays.asList(array));

        if(array.length!=myset.size())
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public static void main(String[] args)
    {
        Integer [] array = { 1, 2, 3, 6, 4, 9, 8, 1};
        System.out.println(solution(array));

    }
}

true

Complexity Analysis

Time Complexity

O(n) where “n” is the size of the array.

Space Complexity

O(n) as the space used by a hash table is linear with the number of elements in it.