how to check if an array contains only distinct elements with time complexity n logn

you can quicksort the array (n log(n)), then finding duplicates becomes linear (only need to check consecutive elements).

Use a sorting algorithm (e.g. mergesort which has O(n log n)) and then check for consecutive elements that are equal. Or modify the merge step of mergesort to detect equal elements. Also, use size_t for indices, not int.

Assuming you can alter array, do that first (n log n provided you're using a good algorithm). Next, walk array and compare sequential elements (n).

If you use C++, then this is a way:

#include <set>

bool hasDuplicates(int array[], int n)
{
    std::set<int> no_duplicates(array, array + n);
    return no_duplicates.size() != n;
}

You can use Sorting, Set or even Unordered Map to achieve your task.

• If you can alter the contents of the array, prefer sorting
• If you can't alter the contents of the array, set is a good choice
• If you can't alter the contents of the array & want to achieve O(N) complexity prefer unordered map

Using sorting

// Checking duplicates with Sorting, Complexity: O(nlog(n))
bool checkDuplicatesWithSorting(int array[], int n)
{
 sort(array, array+n);
 for(int i = 1; i < n; i++ )
 {
    if(array[i]==array[i-1])
        return true;
 }
 return false;
}

Using Set

// Checking duplicates with a Set, Complexity: O(nlog(n))
bool checkDuplicatesWithSet(int array[], int n)
{
 set <int> s(array, array+n);
 return s.size() != n;
}

Using Unordered Map

// Checking duplicates with a Unordered Map, Complexity: O(n) (Average Case)
bool checkDuplicatesWithHashMap(int array[], int n)
{
 unordered_map<int, bool>uo_map;
 for(int i=0;i<n;i++){
    if(uo_map.find(array[i]) ==  uo_map.end())
        uo_map[array[i]] = true;
    else return true;
 }
 return false;
}

Live Code