Common elements in all rows of a given matrix

You are given a m*n row wise sorted matrix. The task is to find the common element in all rows of given matrix.

Examples:

Input :  mat[3][4]={{1,3,5,6},
                    {3,4,7,8},
                    {1,2,3,4}}
Output:  3

Input :  mat[4][4]={{2,3,4,5},
                    {1,2,3,6},
                    {2,3,5,6},
                    {1,2,3,4}}
Output: 2 3

Approaches:
A simple solution for this problem is to use Hasing.
Create hash array of size n . Now one by one traverse each row and calculate frequency of each element.
Ater that traverse hash array again and if frequency of any element is equal to m (number of rows) that means this element is common in all row.
This condition holds if elements are not repeated in rows, if elements are repeated in rows then in each row count each element only once.
Time complexity for this approach is O(m*n) and space complexity is O(n).

An efficient solution for this problem is to use Binary Search.
The idea is to select each element of first row one by one and since all rows are sorted so search that element in all remaining rows, if element is found in all remaining rows that means this is the common element in all rows.

// C++ implementation of algorithm
#include <bits/stdc++.h>
#define MAX 100
using namespace std;

// Function to find common elements in all rows
void common(int mat[][MAX], int m, int n)
{
    // One by one select each element of first row
    for (int j = 0; j < n; j++)
    {
        // mat[0][j] is key element that we have to search in remaining rows
        int key = mat[0][j];

        // Flag which tells if element is found or not
        bool flag = true;

        // Search element in remaining rows
        for (int i = 1; i < m; i++)
        {
            // binary_search() is a C++ STL function
            // If key is present in array, it returns true; else, false
            // If element is not found in any row, we do not need to search
            // in remaining rows
            if (!binary_search(mat[i], mat[i] + n, key))
            {
                flag = false;
                break;
            }
        }

        // If flag is true, that means element is present in all rows
        if (flag)
            cout << key << " ";
    }
}

// Driver program to run case
int main()
{
    int m = 4, n = 4;
    int mat[][MAX] = {{2, 3, 4, 5},
                     {1, 2, 3, 6},
                     {2, 3, 5, 6},
                     {1, 2, 3, 4}};
    common(mat, m, n);
    return 0;
}

Output:

2 3

Time complexity: O(m*n*(logn))
Space complexity: O(m*n)

Similar Reads