Common elements in all rows of a given matrix in C++

May 4, 2022

Common elements in all row of a given matrix in C++

Here, in this page we will discuss the program to find the common elements in all row of a given matrix in C++ Programming language. We will discuss various methods to solve the given problem.

Method Discussed :

Method 1 : Naive Approach
Method 2 : Using Hash-map

Let’s discuss them one by one in brief,

Method 1:

In this method we will check for every element that, if it is present in other rows or not.

Time and Space Complexity :

Time complexity: O(N*M)
Space complexity: O(1)

Method 1 : Code in C++

Run

#include <bits/stdc++.h>
using namespace std;
#define N 5

int findMaxValue(int mat[][N])
{
    int maxValue = INT_MIN;

    for (int a = 0; a < N - 1; a++)
    for (int b = 0; b < N - 1; b++)
        for (int d = a + 1; d < N; d++)
        for (int e = b + 1; e < N; e++)
            if (maxValue < (mat[d][e] - mat[a][b]))
                maxValue = mat[d][e] - mat[a][b];
 
    return maxValue;
}
 
int main()
{
int mat[N][N] = {
                { 1, 2, -1, -4, -20 },
                { -8, -3, 4, 2, 1 },
                { 3, 8, 6, 1, 3 },
                { -4, -1, 1, 7, -6 },
                { 0, -4, 10, -5, 1 }
            };
    cout << "Maximum Value is " << findMaxValue(mat);
 
    return 0;
}

Output :

Maximum Value is 18

Method 2:

Initially insert all elements of the first row in an map.
For every other element in remaining rows, we check if it is present in the map.
If it is present in the map and is not duplicated in current row, we increment count of the element in map by 1, else we ignore the element.
If the currently traversed row is the last row, we print the element if it has appeared m-1 times before.

Time and Space Complexity :

Time complexity: O(M*N)
Space complexity: O(N)

Method 2 : Code in C++

Run

#include <bits/stdc++.h>
using namespace std;
#define M 4
#define N 5
 
void printCommonElements(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] =
    {
        {10, 20, 10, 40, 80},
        {30, 70, 80, 50, 10},
        {80, 70, 70, 30, 10},
        {80, 10, 20, 70, 90},
    };
 
    printCommonElements(mat);
 
    return 0;
}

Output :

80 10