Common Elements in All Rows of a Given Matrix

Understanding the Problem

The goal is to find common elements present in all rows of a given matrix.

Method 1: Using Hashing

This method uses a hash table to count occurrences of elements.

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

void commonElements(int matrix[][100], int rows, int cols) {
    unordered_map countMap;

    // Count occurrences of each element in the first row
    for (int j = 0; j < cols; j++) {
        countMap[matrix[0][j]] = 1;
    }

    // Count occurrences in subsequent rows
    for (int i = 1; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (countMap[matrix[i][j]] == i) {
                countMap[matrix[i][j]]++;
            }
        }
    }

    // Print common elements
    cout << "Common elements: ";
    for (auto &pair : countMap) {
        if (pair.second == rows) {
            cout << pair.first << " ";
        }
    }
    cout << endl;
}

int main() {
    int matrix[100][100] = {
        {1, 2, 3, 4},
        {2, 3, 5, 6},
        {3, 4, 5, 7}
    };
    int rows = 3, cols = 4;
    commonElements(matrix, rows, cols);
    return 0;
}
            

Output:

Common elements: 3

Method 2: Using Sorting

This method sorts each row and finds common elements.

#include <iostream>
#include <algorithm>
using namespace std;

void commonElements(int matrix[][100], int rows, int cols) {
    // Sort the first row
    sort(matrix[0], matrix[0] + cols);

    for (int i = 1; i < rows; i++) {
        int j = 0, k = 0;
        int common[100], index = 0;

        // Sort the current row
        sort(matrix[i], matrix[i] + cols);

        // Find common elements
        while (j < cols && k < cols) {
            if (matrix[0][j] == matrix[i][k]) {
                common[index++] = matrix[0][j];
                j++;
                k++;
            } else if (matrix[0][j] < matrix[i][k]) {
                j++;
            } else {
                k++;
            }
        }

        // Copy common elements back to the first row
        for (int m = 0; m < index; m++) {
            matrix[0][m] = common[m];
        }
        cols = index; // Update the number of common elements
    }

    // Print common elements
    cout << "Common elements: ";
    for (int i = 0; i < cols; i++) {
        cout << matrix[0][i] << " ";
    }
    cout << endl;
}

int main() {
    int matrix[100][100] = {
        {1, 2, 3, 4},
        {2, 3, 5, 6},
        {3, 4, 5, 7}
    };
    int rows = 3, cols = 4;
    commonElements(matrix, rows, cols);
    return 0;
}
            

Output:

Common elements: 3

Method 3: Using Set Intersection

This method uses sets to find common elements across rows.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

void commonElements(int matrix[][100], int rows, int cols) {
    set commonSet;

    // Initialize the set with the first row
    for (int j = 0; j < cols; j++) {
        commonSet.insert(matrix[0][j]);
    }

    // Intersect with subsequent rows
    for (int i = 1; i < rows; i++) {
        set currentRowSet;
        for (int j = 0; j < cols; j++) {
            currentRowSet.insert(matrix[i][j]);
        }

        // Keep only common elements
        for (auto it = commonSet.begin(); it != commonSet.end();) {
            if (currentRowSet.find(*it) == currentRowSet.end()) {
                it = commonSet.erase(it);
            } else {
                ++it;
            }
        }
    }

    // Print common elements
    cout << "Common elements: ";
    for (auto elem : commonSet) {
        cout << elem << " ";
    }
    cout << endl;
}

int main() {
    int matrix[100][100] = {
        {1, 2, 3, 4},
        {2, 3, 5, 6},
        {3, 4, 5, 7}
    };
    int rows = 3, cols = 4;
    commonElements(matrix, rows, cols);
    return 0;
}
            

Output:

Common elements: 3