Matrix: Find common elements in all rows of a given matrix

Problem Statement:

You are given a 2D matrix of size n * m.
You need to find all the common elements present in all rows.

Example:

Input:

1 2 3 4
5 4 6 1
9 7 1 4
5 4 1 9

Output:

1 4 number are present in all rows

Solution Explanation:

Simple solution is to use maps.

Insert all the elements of the first row into map.

The for all the elements of the next row, check if it is present in the map, and if present increment the element in map by 1.

Then repeat for all the rows.

Once the traversing of last row is completed, then print the elements that has appeared m-1 times.

Time Complexity: O(m * n)
Space Complexity: O(n)

Code Solution

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

#define M 4
#define N 4

void solution(int mat[M][N])
{
    unordered_map<int, int> mp;

    for (int j = 0; j < N; j++)
        mp[(mat[0][j])] = 1;

    for (int i = 1; i < M; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (mp[(mat[i][j])] == i)
            {
                mp[(mat[i][j])] = i + 1;

                if (i==M-1 && mp[(mat[i][j])]==M)
                  cout << mat[i][j] << " ";
            }
        }
    }
}

int main()
{
    int mat[M][N] =
    {
        {1, 2, 3, 4},
        {5, 4, 6, 1},
        {9, 7, 1, 4},
        {5, 4, 1, 9},
    };

    solution(mat);

    return 0;
}

Output

4 1