Common elements in all rows of a given matrix

Table of Contents

Problem Statement

“Common elements in all rows of a given matrix” problem state that, you are given a matrix of M*N. The problem statement asks to find out all the common elements in a given matrix in each row of the matrix in O(M*N) time.

Example

arr[]={{12, 1, 4, 5, 9},

{3, 8, 0, 4, 1},

{2, 7, 4, 1, 5},

{6, 3, 1, 9, 4}}

1 4

Explanation: 1 and 4 are the only elements of a matrix that are present in each row of a given matrix.

Algorithm to find common elements in all rows of a given matrix

1. Declare a map.
2. Assign all the values of a first row to 1 and stored into the map.
3. Traverse the matrix from the 2nd row of the matrix.
    1. Check if the map contains the current value of the matrix and also the current matrix’s value in a map should be equal to i.
    2. If true, then increase the value of the current matrix’s element frequency in a map by 1.
    3. Put the condition if this is the last row then print all those elements which are common in each row.

Explanation

We are given a matrix of M*N size. Our task is to find out all the common elements which are also present in each row of the given matrix. We will be solving this using the hashing technique. Using the naive approach will cost us more time complexity than this code. So, we will be solving it in O(M*N) time complexity. We will be declaring a map. In that map, we will be initializing the values to 1 and then proceed with the ahead values in a matrix.

Take a map, we will start with the first row of the matrix and initialize all the values of only first row elements to 1. This is because when we traverse for the second row in a matrix. And if we have the element in a map the same as present in a second row. This means we have found the common element for now which is present in only two rows for now.

Start traversing the matrix now from the second row, we will be checking if each element of every row is present in the map, if it is present in the map then it means this is the 2^nd occurrence of that element in a matrix consecutively in a second row. We will be checking if each element frequency we picked is equal to the current row. We will update the value of that element’s frequency and increase it by 1 in a map. So for each traversal, we will be checking its frequency if it is equal to i’th row means it is consecutively present in all the rows, then we will be printing all those values of a matrix when we are in the last row traversal.

Common elements in all rows of a given matrix

Code

C++ Code to find common elements in all rows of a given matrix

#include<iostream>
#include<unordered_map>

#define M 4
#define N 5
using namespace std;


void getCommonElementinRow(int matrix[M][N])
{
    unordered_map<int, int> MAP;

    for (int j = 0; j < N; j++)
        MAP[matrix[0][j]] = 1;

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

                if (i==M-1)
                    cout << matrix[i][j] << " ";
            }
        }
    }
}
int main()
{
    int matrix[M][N] = {{12, 1, 4, 5, 9},
        {3, 8, 0, 4, 1},
        {2, 7, 4, 1, 5},
        {6, 3, 1, 9, 4}
    };

    getCommonElementinRow(matrix);

    return 0;
}

1 4

Java code to find common elements in all rows of a given matrix

import java.util.HashMap;

class CommonElementsinRow
{
    private static int M = 4;
    private static int N =5;

    static void getCommonElementinRow(int matrix[][])
    {

        HashMap<Integer,Integer> MAP = new HashMap<>();

        for (int j = 0; j < N; j++)
            MAP.put(matrix[0][j],1);

        for (int i = 1; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (MAP.get(matrix[i][j]) != null && MAP.get(matrix[i][j]) == i)
                {

                    MAP.put(matrix[i][j], i + 1);

                    if (i == M - 1)
                        System.out.print(matrix[i][j] + " ");
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int matrix[][] =
        {
            {12, 1, 4, 5, 9},
            {3, 8, 0, 4, 1},
            {2, 7, 4, 1, 5},
            {6, 3, 1, 9, 4}
        };
        getCommonElementinRow(matrix);
    }
}

1 4

Complexity Analysis

Time Complexity

O(m * n) where “m” and “n” is the number of rows and columns in the matrix. Since we use HashMap we can perform insertion and other operations in O(1) time complexity. Thus this make an algorithm to run in O(N*M) time complexity.

Space Complexity

O(m * n) where “m” and “n” is the number of rows and columns in the matrix. Since the initial input itself is of size N*M, we say the space complexity is O(N*M).