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

 
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 🙂
 

Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
nogre
Guest
nogre

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
PythonFreak

nice