Find common elements present in all rows of a matrix

In this post, we will see how to find common elements present in all rows of a given MxN matrix. The solution should traversal the matrix once and print all commons elements in O(M*N) time.


 

For example,


Input:

{ 2, 4, 3, 8, 7 }
{ 4, 7, 1, 3, 6 }
{ 3, 5, 2, 1, 3 }
{ 4, 5, 0, 2, 3 }

Output: 8

 

Naive solution is to check if each element is present in all rows or not. The time complexity of this solution is O(M2 * N2), which is pretty bad.

Efficient solution is to use Map. We start by inserting every element of the first row in an empty map. Then for every element in the remaining rows, if they are present in the map and is occurring for the first time in current row, we increment its value in map by 1. Finally for the last row, we print the element if it has already appeared M-1 times.

C++

Download   Run Code

Output:

3

Java

Download   Run Code

Output:

3

 
Author: Aditya Goel

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of