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 –

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 –

Output:

Common elements are: 6 1

(1 votes, average: 5.00 out of 5)

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 🙂

Subscribe
Notify of
Guest

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

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.

Guest
PythonFreak

nice