Find all common elements present in every row of given matrix

Given a M x N matrix, find all common elements present in every row.


 

For example,


Input:

[ 7  1  3  5  3  6 ]
[ 2  3  6  1  1  6 ]
[ 6  1  7  2  1  4 ]
[ 6  6  7  1  3  3 ]
[ 5  5  6  1  5  4 ]
[ 3  5  6  2  7  1 ]
[ 4  1  4  3  6  4 ]
[ 4  6  1  7  4  3 ]

Output: Common elements are 1 and 6

 
The idea is very simple and efficient. We create an empty map and insert all elements of the first row in the map with their value set as 1. Now for each element of remaining rows, we check if it is present in the map or not. If the element is present in the map, we check its count to see if it is present in all previous rows or not. If yes, we increment its count by 1 else we ignore the element. One special case we need to handle that any duplicate entry in the same row should not get inserted into the map again.

 
C++ implementation –
 

Download   Run Code

Output:

Common elements are: 6 1

 
The time complexity of above solution is O(M * N).

 
Here’s another solution that uses set data structure. The idea is to insert all elements of the first row into a set. Then for each of the remaining rows, we simply remove elements from the set that are not present in the current row using another set.

 
C++ implementation –
 

Download   Run Code

Output:

Common elements are: 6 1

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

Loading...

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

avatar
  Subscribe  
newest oldest most voted
Notify of
Max
Guest

We may use Set as a base for a solution.
Java 8: https://ideone.com/4WoUkt

nogre
Guest

I liked this little exercise. Here’s a Python3 solution:
https://ideone.com/gkmIKV

I’m certain it could be more pythonic and efficient, but I tried to write it so anyone could understand it.

PythonFreak
Guest

nice