Check if an array contains distinct elements in C++

In this tutorial, we will learn to check if an array contains at least one duplicate element or if all of its elements are distinct. We will assume that all elements of the array are integer values, and we will return true or false as the output.

We will solve this problem using 2 methods:

1. Using Sorting
2. Using Hashmap

Using Sorting

In this method, we first sort the array using the C++ STL sort() function and then traverse through the array to check if any 2 adjacent elements are the same. If we found 2 same adjacent elements, it means the array has at least 1 duplicate element. Otherwise, the array has only distinct elements.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    bool atleastOneDuplicate(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        for(int i=0; i<arr.size()-1; i++){
            if(arr[i] == arr[i+1]){
                return true;
            }
        }
        return false;
    }
};


int main()
{
vector<int> arr = {1,5,7,1,2};
Solution s;
bool ans = s.atleastOneDuplicate(arr);
ans?cout << "array has atleast one duplicate element" : cout << "array has only distinct elements";
}

Output:

array has atleast one duplicate element

Complexity:

Time Complexity: O(nlogn)
Space Complexity: O(1)

Using Hashmap

In this method, we first create a hashmap and start traversing through the array. In every iteration, we check if the element already exists in the hashmap, and if it does, we will return true otherwise, we will insert the element into the hashmap.

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool atleastOneDuplicate(vector<int>& arr) {
        unordered_map<int, int> hmap;
        for(int i=0; i<arr.size(); i++){
            if(hmap.find(arr[i]) != hmap.end()){
                return true;
            }else{
                hmap.insert({arr[i], i});
            }
        }
        return false;
    }
};


int main()
{
vector<int> arr = {1,5,7,2};
Solution s;
bool ans = s.atleastOneDuplicate(arr);
ans?cout << "array has atleast one duplicate element" : cout << "array has only distinct elements";
}

Output:

array has only distinct elements

Complexity:

Time Complexity: O(n)
Space Complexity: O(n)