Example: Find Common Element Using Hashing in C++

// Find Common Element Using Hashing
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

// Function to find common element using hashing
int findCommonElement_Hashing(const vector<vector<int>>& matrix) {
    int R = matrix.size();
    if (R == 0) return -1; // Empty matrix

    int C = matrix[0].size();
    if (C == 0) return -1; // Empty rows

    unordered_map<int, int> counts; // Map to store element counts

    // Add elements of the first row to the map with count 1
    for (int j = 0; j < C; ++j) {
        counts[matrix[0][j]] = 1;
    }

    // Iterate through the remaining rows (from the second row)
    for (int i = 1; i < R; ++i) {
        // Iterate through elements of the current row
        for (int j = 0; j < C; ++j) {
            // If the element is present in the map and its count matches the current row index
            // This ensures we count each unique occurrence from distinct rows.
            // Example: If counts[x] == i, it means x was found in rows 0 to i-1.
            // Now if we find x in row i, its count can be incremented to i+1.
            if (counts.count(matrix[i][j]) && counts[matrix[i][j]] == i) {
                counts[matrix[i][j]]++;
            }
        }
    }

    // Check which element has a count equal to the number of rows
    for (auto const& pair : counts) {
        if (pair.second == R) {
            return pair.first; // Found a common element
        }
    }

    return -1; // No common element found
}

int main() {
    // Step 1: Define a sample matrix
    vector<vector<int>> matrix1 = {
        {1, 2, 3, 4, 5},
        {2, 3, 4, 5, 6},
        {3, 4, 5, 6, 7},
        {4, 5, 6, 7, 8}
    };
    cout << "Matrix 1:" << endl;
    for (const auto& row : matrix1) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    cout << "Common element (Hashing): " << findCommonElement_Hashing(matrix1) << endl << endl;

    vector<vector<int>> matrix2 = {
        {1, 2, 3, 4},
        {1, 2, 3, 4},
        {1, 2, 3, 4}
    };
    cout << "Matrix 2:" << endl;
    for (const auto& row : matrix2) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    cout << "Common element (Hashing): " << findCommonElement_Hashing(matrix2) << endl << endl;

    vector<vector<int>> matrix3 = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    cout << "Matrix 3:" << endl;
    for (const auto& row : matrix3) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    cout << "Common element (Hashing): " << findCommonElement_Hashing(matrix3) << endl << endl;

    return 0;
}