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,


{ 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.


Download   Run Code




Download   Run Code



Author: Aditya Goel

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

Notify of