What is the fastest way to see if an array has two common elements?

user_9194639 0
Viewed 675

Suppose that we have a very long array, of, say, int to make the problem simpler.

What is the fastest way (or just a fast way, if it's not the fastest), in C++ to see if an array has more than one common elements in C++?

To clarify, this function should return this:

[2, 5, 4, 3] => false
[2, 8, 2, 5, 7, 3, 4] => true
[8, 8, 5] => true
[1, 2, 3, 4, 1, 7, 1, 1, 7, 1, 2, 2, 3, 4] => true
[9, 1, 12] => false

One strategy is to loop through the array and for each array element loop through the array again to check. However, this can be very costly and expensive (literally O(n^2)). Is there any better way?

c++17 duplicates arrays algorithm c++
3 Answers

(✠Update Below) Insert the array elements to a std::unordered_set and if the insertion fails, it means you have duplicates.

Something like as follows:

#include <iostream>
#include <vector>
#include <unordered_set>

bool has_duplicates(const std::vector<int>& vec)
{
    std::unordered_set<int> set;
    for (int ele : vec)
        if (const auto [iter, inserted] = set.emplace(ele); !inserted)
            return true; // has duplicates!
    return false;
}

int main()
{
    std::vector<int> vec1{ 1, 2, 3 };
    std::cout << std::boolalpha << has_duplicates(vec1) << '\n'; // false

    std::vector<int> vec2{ 12, 3, 2, 3 };
    std::cout << std::boolalpha << has_duplicates(vec2) << '\n'; // true
}

✠Update: As discussed in the comments, this can or may not be the fastest solution. In OP's case, as explained in Marcus Müller's answer, anO(N·log(N)) method would be better, which we can achieve by having a sorted array check for dupes.

Here is a quick benchmark that I made for the two cases "UnorderedSetInsertion" and the "ArraySort". Following are the result for GCC 10.3, C++20, O3:

enter image description here

user_96098400

This is nearly just a sorting problem, just that you can abort the sorting once you've hit a single equality and return true.

So, if you're memory-limited (That's often the case, not actually time-limited), an in-place sorting algorithm that aborts when it encounters to identical elements will do; so, std::sort with a comparator function that raises an exception when it encounters equality. Complexity would be O(N·log(N)), but let's be honest here: the fact that this is probably less indirect in memory addressing then the creation of a tree-like bucket structure might help. In that sense, I can only recommend you actually compare this to JeJos solution – that looks pretty reasonable, too!

The thing here is that there's very likely not a one-size-fits-all solution: what is fastest will depend on the amount of integers we're talking about. Even quadratic complexity might be better than any of our "clever" answers if that keeps memory access nice and linear – I'm almost certain your speed here is not bounded by your CPU, but by the amount of data you need to shuffle to and from RAM.

user_44333860

How about binning data (or create a histogram), and check for mode of the resultant data. A mode > 1 indicates a repeat value.

user_163463670
Related