Common Elements - C++ Solution

1. Introduction

In this post, we will explore an interesting problem related to matrix processing - finding common elements present in all rows of an M × N integer matrix. This problem tests our ability to efficiently process and compare elements across different rows of a matrix.

Problem

Given an M × N integer matrix, the goal is to find all the common elements that appear in every row of the matrix. The solution should traverse the matrix only once and return the list of common elements.

2. Solution Steps

1. Use a hash table to keep track of the counts of elements in each row.

2. Traverse each row and update the count for each element.

3. Keep track of the row index to ensure we only consider the elements that appear in all rows.

4. After traversing all rows, iterate through the hash table to find the elements that have a count equal to the number of rows, which are the common elements.

3. Code Program

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

// Function to find common elements in all rows of the matrix
vector<int> findCommonElements(const vector<vector<int>>& matrix) {
    unordered_map<int, int> elementCount;
    int M = matrix.size();

    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < matrix[i].size(); ++j) {
            if (i == 0) {
                // For the first row, add all elements
                elementCount[matrix[i][j]] = 1;
            } else if (elementCount[matrix[i][j]] == i) {
                // Increment count only if the element was present in all previous rows
                elementCount[matrix[i][j]]++;
            }
        }
    }

    vector<int> commonElements;
    for (const auto& kv : elementCount) {
        if (kv.second == M) {
            commonElements.push_back(kv.first);
        }
    }

    return commonElements;
}

int main() {
    vector<vector<int>> matrix = {
        {7, 1, 3, 5, 3, 6},
        // ... (other rows)
    };

    vector<int> common = findCommonElements(matrix);

    // Output the common elements
    cout << "Common Elements: ";
    for (int val : common) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

Output:

Common Elements: 1 6

Explanation:

The function findCommonElements processes the matrix to find elements common to all rows. It uses a hash table to count the occurrences of each element row-wise. While processing each row, it ensures that an element's count is incremented only if it was present in all previous rows. Finally, it returns those elements whose count equals the number of rows, indicating they are common across all rows. For the given matrix, the common elements are {1, 6}.