Home » Algorithms

Check duplicate elements in an array of n elements

In this tutorial, we are going to learn how to check whether there is any duplicate number in a given array or not? By Radib Kar Last updated : August 16, 2023

Problem statement

Given an array of n numbers, Check whether there is any duplicate or not.

Solution approach

This is a searching problem which can be solved using brute force approach. But here we are going to see use of hash table to solve such searching problems at lower time complexity.

Algorithm

Hash table is a simple and effective data structure to solve searching problems in O(1) time complexity. Hash tables can be easily built using STL in C++.

The algorithm to solve the problem:

1. Create hash table.
2. Set element pointer to 0. (starting from array[0], first element)
3. Search for the element in the Hash table.
4. If found there is duplicate. Print "duplicate found" & return from program.
5. Else insert the element to the hash table.
6. If end of the array is reached, exit and print "no duplicate found".
7. Else increase the element pointer and go to step 3 (continue).

Time & Space Complexity

• Time complexity: O(1) for searching hash table, O(n) overall
• Space complexity: O(n) (for creating hash table)

Create hash table using STL

Hash table is created using unordered_set in STL.

C++ program to check duplicate elements in an array of n elements

#include <bits/stdc++.h>
using namespace std;

void checkDuplicate(unordered_set<int> hash, int* a, int n)
{
    for (int i = 0; i < n; i++) {
        if (hash.find(a[i]) == hash.end()) {
            hash.insert(a[i]);
        }
        else {
            printf("Duplicate found.....\n");
            return;
        }
    }
    printf("No duplicates found........\n");
}

int main()
{
    int n, x, count = 0;

    printf("how many elements do you want in your array\n");
    scanf("%d", &n);

    printf("enter elements\n");
    // dynamic array created
    int* a = (int*)(malloc(sizeof(int) * n));
    // creating hash table
    unordered_set<int> hash;
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    // function to check duplicate exists or not
    checkDuplicate(hash, a, n);
    return 0;
}

Output

First run:
how many elements do you want in your array
5
enter elements
1 2 3 4 5
No duplicates found........

Second run:
how many elements do you want in your array
6
enter elements
3 2 1 3 5 6
Duplicate found.....