What is the fastest way to find the positions of the first common entry in two vectors in c++?

Question

I have two vectors u = {32, 25, 13, 42, 55, 33} and v = {18, 72, 53, 39, 13, 12, 28} for which I would like to determine the position of their first common entry, 13. For these example vectors, these positions are 3 and 5. What is the fastest way to find these positions? I have to do this operation many-many times.

Answer 1

Assuming you don't have duplicate, you might use the following:

std::pair<std::size_t, std::size_t>
common_entry_indexes(const std::vector<int>& u, const std::vector<int>& v)
{
    const std::size_t min_size = std::min(u.size(), v.size());
    std::map<int, std::size_t> s; // might be `std::unordered_map`

    for (std::size_t i = 0; i != min_size; ++i)
    {
         if (auto [it, inserted] = s.insert({u[i], i}); !inserted) { return {i, it->second}; }
         if (auto [it, inserted] = s.insert({v[i], i}); !inserted) { return {it->second, i}; }
    }
    for (std::size_t i = min_size; i != u.size(); ++i)
    {
         if (auto [it, inserted] = s.insert({u[i], i}); !inserted) { return {i, it->second}; }
    }
    for (std::size_t i = min_size; i != v.size(); ++i)
    {
         if (auto [it, inserted] = s.insert({v[i], i}); !inserted) { return {it->second, i}; }
    }
    return {-1, -1}; // Not found
}

Demo

• Duplicate might be handled with extra check.
• Complexity should be O(max(N, M) * log(N + M)) with map (and O(max(N, M)) in average with std::unordered_map)

Answer 2

If not the fastest, then surely the simplest (assuming, as in your question, you want 1-based indexing, so we can use {0, 0} as a "not found" signal and the size_t type for the indexes):

#include <utility>   // For std::pair
#include <algorithm> // For std::find
#include <vector>
#include <iostream>

std::pair<size_t, size_t> FirstCommon(std::vector<int>& a, std::vector<int>& b)
{
    for (size_t i = 0; i < a.size(); ++i) {
        auto f = std::find(b.begin(), b.end(), a.at(i));
        if (f != b.end()) return { i + 1, f - b.begin() + 1 }; // Found a[i] in b
    }
    return { 0, 0 };
}

int main()
{
    std::vector<int> u = { 32, 25, 13, 42, 55, 33 };
    std::vector<int> v = { 18, 72, 53, 39, 13, 12, 28 };
    auto match = FirstCommon(u, v);
    std::cout << "Position is {" << match.first << "," << match.second << "}." << std::endl;
    return 0;
}

Answer 3

In addition to "small-sized vectors" and "no duplicates", if it is the case that your keys are always within a known, memory-supported range (e.g. "no key will ever be greater than 10.000"), then you can leverage this extra info to achieve an O(max(N,M)) (linear time!) solution ( @Jarod's is O(max(N,M) * log(N+M)) and @Adrian's is O(N*M)).

First, establish a large enough prime (i.e. a prime larger than the largest key) and then start to build a hashmap up to the point where the first collision happens.

std::pair<size_t, size_t> findFirstMatch(const std::vector<int>& u, const std::vector<int>& v, const int& prime) {
    std::vector<size_t> hashmap(prime, INT_MAX);    // ---> 'INT_MAX' returned if no common entries found.
    size_t smallerSz = std::min(u.size(), v.size());
    std::pair<size_t, size_t> solution = { INT_MAX, INT_MAX };
    bool noCollision = true;

    // Alternate checking, to ensure minimal testing:
    for (size_t i = 0; i < smallerSz; ++i) {
        //One step for vetor u:
        size_t& idx = hashmap[u[i] % prime];
        if (idx < INT_MAX) {    // ---> Collision!
            solution = { i, idx };
            noCollision = false;
            break;
        }
        idx = i;

        //One step for vector v:
        idx = hashmap[v[i] % prime];
        if (idx < INT_MAX) {    // ---> Collision!
            solution = { idx, i };
            noCollision = false;
            break;
        }
        idx = i;
    }

    //If no collisions so far, then the remainder of the larger vector must still be checked:
    if(noCollision){
        const bool uLarger = u.size() > v.size();
        const std::vector<int>& largerVec = (uLarger) ? u : v;
        for (size_t i = smallerSz; i < largerVec.size(); ++i) {
            size_t& idx = hashmap[largerVec[i] % prime];
            if (idx < INT_MAX) {    // ---> Collision!
                if (uLarger) solution = { i, idx };
                else         solution = { idx, i };
                break;
            }
            idx = i; 
        }
    }
    return solution;
}

USAGE

int main()
{
    std::vector<int> u = { 32, 25, 13, 42, 55, 33 }, v = { 18, 72, 53, 39, 13, 12, 28 };
    const int prime = 211; // ---> Some suitable prime...

    std::pair<size_t, size_t> S = findFirstMatch(u, v, prime);
    std::cout << "Solution = {" << S.first << "," << S.second << "}.";
    return 0;
}

It outputs "{2, 4}" instead of "{3, 5}" because the first index is 0. Feel free to modify it.