Common elements in all rows of a given matrix - GeeksforGeeks

Common elements in all rows of a given matrix - GeeksforGeeks
Given an m x n matrix, find all common elements present in all rows in O(mn) time and one traversal of matrix.

The time complexity of this solution is O(m * n) and we are doing only one traversal of the matrix.

void printCommonElements(int mat[M][N])

{

    unordered_map<int, int> mp;

 

    // initalize 1st row elements with value 1

    for (int j = 0; j < N; j++)

        mp[mat[0][j]] = 1;

 

    // traverse the matrix

    for (int i = 1; i < M; i++)

    {

        for (int j = 0; j < N; j++)

        {

            // If element is present in the map and

            // is not duplicated in current row.

            if (mp[mat[i][j]] == i)

            {

               // we increment count of the element

               // in map by 1

                mp[mat[i][j]] = i + 1;

 

                // If this is last row

                if (i==M-1)

                  cout << mat[i][j] << " ";

            }

        }

    }

}

Another solution is to sort all rows in the matrix and use similar approach as discussed here. Sorting will take O(mnlogn) time and finding common elements will take O(mn) time. So overall time complexity of this solution is O(mnlogn)

Read full article from Common elements in all rows of a given matrix - GeeksforGeeks