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 efficiently finds common elements by performing set intersections between rows.

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

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

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

    // Perform intersection with each subsequent row
    for (int i = 1; i < rows; i++) {
        currentRowSet.clear();
        
        // Create set for current row
        for (int j = 0; j < cols; j++) {
            currentRowSet.insert(matrix[i][j]);
        }

        // Temporary set to store intersection
        set<int> tempSet;
        
        // Find intersection between commonSet and currentRowSet
        set_intersection(
            commonSet.begin(), commonSet.end(),
            currentRowSet.begin(), currentRowSet.end(),
            inserter(tempSet, tempSet.begin())
        );

        // Update commonSet with the intersection result
        commonSet = tempSet;
        
        // Early exit if no common elements found
        if (commonSet.empty()) {
            break;
        }
    }

    // Print common elements
    cout << "Common elements: ";
    if (commonSet.empty()) {
        cout << "None";
    } else {
        for (int num : commonSet) {
            cout << num << " ";
        }
    }
    cout << endl;
}

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

Output:

Common elements: 5

Explanation:

This method works by:

• Creating a set from the first row to store potential common elements
• Iterating through each subsequent row and creating a set of its elements
• Performing set intersection between the common set and current row set
• Updating the common set with the intersection result
• Early termination if the common set becomes empty

The algorithm has O(rows*cols*log(cols)) time complexity due to set operations, which is efficient for matrices with sorted or partially sorted rows.

Key advantages:

1. Automatically handles duplicate elements within rows
2. Maintains elements in sorted order
3. Provides early termination when no common elements exist
4. Works well with both small and large matrices