Calculate Number of Elements that Belong in both Vectors in C++

Question

Our task is to calculate the number of elements that belong to both of the lists. For example, for the lists

vector<int> arr1{5,2,8,9}
vector<int> arr2{3,2,9,5}

The answer would 3 because the numbers 2, 5 and 9 belong to both of the lists. I want to make this algorithm in the least possible time complexity - O(nlogn). The goal is for me to sort the list and then iterate through both of them at once and find the common elements.

Here is what I have so far:

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

int main() {
    int counter;
    vector<int> arr1{ 5, 2, 8, 9 };
    vector<int> arr2{3, 2, 9, 5};

    sort(arr1.begin(), arr1.end()); // 2, 5, 8, 9
    sort(arr2.begin(), arr2.end()); // 2, 3, 5, 9

    for (int i = 0; i < 4; i++) {
        // insert code here
    }

    cout << counter;

    return 0;
}

Any help would be appreciated!

Answer 1

Answer is quite simple, since the arrays are sorted you can have indices running on two arrays, counting when elements are equal, and incrementing when one is smaller than the other.

    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] == arr2[j]) {
            ++counter;
            ++i;
            ++j;
        }

        else if (arr1[i] < arr2[j]) {
            ++i;
        }

        else {
            ++j;
        }
    }

I want you to note that solving this problem using set intersection has expected time of O(n).

Answer 2

It was pointed out to me by Michael, that it can be done in O(N). Instead of sorting you can use two arrays of size N. Traverse one vector to mark elements that appear in it, do the same with the other vector, then traverse those two arrays to count elements that appear in both. All individual steps are O(N), hence in total it is also O(N):

#include <vector>
#include <algorithm>
#include <iostream>
int main() {
    std::vector<int> v1{ 1, 2, 3, 4, 5, 6, 7, 8 };
    std::vector<int> v2{ 5, 7, 9, 10 };

    auto m1 = std::minmax_element(v1.begin(),v1.end());
    auto m2 = std::minmax_element(v2.begin(),v2.end());

    auto min = std::max( *m1.first, *m2.first);  // we only need to consider the max minimum element
    auto max = std::min( *m1.second, *m2.second); // and the min maximum element

    auto get_occurence_vector = [min,max](const std::vector<int>& v) {
        std::vector<bool> result(max-min+1); // max and min included, hence +1
        for (const auto& e : v) {
            int t = e - min;
            if (t >= 0 && t <= max) result[t] = true;
        }
        return result;
    };

    auto occurs_in1 = get_occurence_vector(v1);
    auto occurs_in2 = get_occurence_vector(v2);

    size_t counter = 0;
    for (size_t i = 0;i< occurs_in1.size(); ++i) {
        if (occurs_in1[i] && occurs_in2[i]) {
            std::cout << i + min << "\n";
            ++counter;
        }
    }

    std::cout << "count = " << counter;
}

Output:

5
7
count = 2

It is basically a trade-off between run-time complexity and memory usage. If the range of values in the vectors is huge, but their size is small, then sorting can be more efficient, even though the complexity is worse (remember that complexity is for the limit of large N).

Answer 3

#include <bits/stdc++.h> 
using namespace std; 
#define MAX 100000 
bitset<MAX> bit1, bit2, bit3; 

// Function to return the count of common elements 
int count_common(int a[], int n, int b[], int m) 
{ 

    // Traverse the first array 
    for (int i = 0; i < n; i++) { 

        // Set 1 at position a[i] 
        bit1.set(a[i]); 
    } 

    // Traverse the second array 
    for (int i = 0; i < m; i++) { 

        // Set 1 at position b[i] 
        bit2.set(b[i]); 
    } 

    // Bitwise AND of both the bitsets 
    bit3 = bit1 & bit2; 

    // Find the count of 1's 
    int count = bit3.count(); 

    return count; 
} 

Try this method to solve the problem. It basically runs in O(log min(n,m));

Answer 4

You can use std::set_intersection like:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> v1{ 1, 2, 3, 4, 5, 6, 7, 8 };
    std::vector<int> v2{ 5, 7, 9, 10 };
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::vector<int> v_intersection;

    std::set_intersection(
        v1.begin(), v1.end(),
        v2.begin(), v2.end(),
        std::back_inserter(v_intersection)
    );

    std::cout << v_intersection.size() << std::endl; // output: 2
}