# Common elements in all rows of a given matrix

Given an m x n matrix, find all common elements present in all rows in O(mn) time and one traversal of matrix.**Example:**

Input:mat[4][5] = {{1, 2, 1, 4, 8}, {3, 7, 8, 5, 1}, {8, 7, 7, 3, 1}, {8, 1, 2, 7, 9}, };Output:1 8 or 8 1 8 and 1 are present in all rows.

A **simple solution** is to consider every element and check if it is present in all rows. If present, then print it.

A **better solution** is to sort all rows in the matrix and use similar approach as discussed here. Sorting will take O(mnlogn) time and finding common elements will take O(mn) time. So overall time complexity of this solution is O(mnlogn)**Can we do better than O(mnlogn)?**

The idea is to use maps. We initially insert all elements of the first row in an map. For every other element in remaining rows, we check if it is present in the map. If it is present in the map and is not duplicated in current row, we increment count of the element in map by 1, else we ignore the element. If the currently traversed row is the last row, we print the element if it has appeared m-1 times before.

Below is the implementation of the idea:

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

## C++

`// A Program to prints common element in all` `// rows of matrix` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Specify number of rows and columns` `#define M 4` `#define N 5` `// prints common element in all rows of matrix` `void` `printCommonElements(` `int` `mat[M][N])` `{` ` ` `unordered_map<` `int` `, ` `int` `> mp;` ` ` `// initialize 1st row elements with value 1` ` ` `for` `(` `int` `j = 0; j < N; j++)` ` ` `mp[mat[0][j]] = 1;` ` ` `// traverse the matrix` ` ` `for` `(` `int` `i = 1; i < M; i++)` ` ` `{` ` ` `for` `(` `int` `j = 0; j < N; j++)` ` ` `{` ` ` `// If element is present in the map and` ` ` `// is not duplicated in current row.` ` ` `if` `(mp[mat[i][j]] == i)` ` ` `{` ` ` `// we increment count of the element` ` ` `// in map by 1` ` ` `mp[mat[i][j]] = i + 1;` ` ` `// If this is last row` ` ` `if` `(i==M-1 && mp[mat[i][j]]==M)` ` ` `cout << mat[i][j] << ` `" "` `;` ` ` `}` ` ` `}` ` ` `}` `}` `// driver program to test above function` `int` `main()` `{` ` ` `int` `mat[M][N] =` ` ` `{` ` ` `{1, 2, 1, 4, 8},` ` ` `{3, 7, 8, 5, 1},` ` ` `{8, 7, 7, 3, 1},` ` ` `{8, 1, 2, 7, 9},` ` ` `};` ` ` `printCommonElements(mat);` ` ` `return` `0;` `}` |

## Java

`// Java Program to prints common element in all` `// rows of matrix` `import` `java.util.*;` `class` `GFG` `{` `// Specify number of rows and columns` `static` `int` `M = ` `4` `;` `static` `int` `N =` `5` `;` `// prints common element in all rows of matrix` `static` `void` `printCommonElements(` `int` `mat[][])` `{` ` ` `Map<Integer,Integer> mp = ` `new` `HashMap<>();` ` ` ` ` `// initialize 1st row elements with value 1` ` ` `for` `(` `int` `j = ` `0` `; j < N; j++)` ` ` `mp.put(mat[` `0` `][j],` `1` `);` ` ` ` ` `// traverse the matrix` ` ` `for` `(` `int` `i = ` `1` `; i < M; i++)` ` ` `{` ` ` `for` `(` `int` `j = ` `0` `; j < N; j++)` ` ` `{` ` ` `// If element is present in the map and` ` ` `// is not duplicated in current row.` ` ` `if` `(mp.get(mat[i][j]) != ` `null` `&& mp.get(mat[i][j]) == i)` ` ` `{` ` ` `// we increment count of the element` ` ` `// in map by 1` ` ` `mp.put(mat[i][j], i + ` `1` `);` ` ` `// If this is last row` ` ` `if` `(i == M - ` `1` `)` ` ` `System.out.print(mat[i][j] + ` `" "` `);` ` ` `}` ` ` `}` ` ` `}` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `mat[][] =` ` ` `{` ` ` `{` `1` `, ` `2` `, ` `1` `, ` `4` `, ` `8` `},` ` ` `{` `3` `, ` `7` `, ` `8` `, ` `5` `, ` `1` `},` ` ` `{` `8` `, ` `7` `, ` `7` `, ` `3` `, ` `1` `},` ` ` `{` `8` `, ` `1` `, ` `2` `, ` `7` `, ` `9` `},` ` ` `};` ` ` `printCommonElements(mat);` `}` `}` `// This code contributed by Rajput-Ji` |

## Python3

`# A Program to prints common element` `# in all rows of matrix` `# Specify number of rows and columns` `M ` `=` `4` `N ` `=` `5` `# prints common element in all` `# rows of matrix` `def` `printCommonElements(mat):` ` ` `mp ` `=` `dict` `()` ` ` `# initialize 1st row elements` ` ` `# with value 1` ` ` `for` `j ` `in` `range` `(N):` ` ` `mp[mat[` `0` `][j]] ` `=` `1` ` ` `# traverse the matrix` ` ` `for` `i ` `in` `range` `(` `1` `, M):` ` ` `for` `j ` `in` `range` `(N):` ` ` ` ` `# If element is present in the` ` ` `# map and is not duplicated in` ` ` `# current row.` ` ` `if` `(mat[i][j] ` `in` `mp.keys() ` `and` ` ` `mp[mat[i][j]] ` `=` `=` `i):` ` ` ` ` `# we increment count of the` ` ` `# element in map by 1` ` ` `mp[mat[i][j]] ` `=` `i ` `+` `1` ` ` `# If this is last row` ` ` `if` `i ` `=` `=` `M ` `-` `1` `:` ` ` `print` `(mat[i][j], end ` `=` `" "` `)` ` ` `# Driver Code` `mat ` `=` `[[` `1` `, ` `2` `, ` `1` `, ` `4` `, ` `8` `],` ` ` `[` `3` `, ` `7` `, ` `8` `, ` `5` `, ` `1` `],` ` ` `[` `8` `, ` `7` `, ` `7` `, ` `3` `, ` `1` `],` ` ` `[` `8` `, ` `1` `, ` `2` `, ` `7` `, ` `9` `]]` `printCommonElements(mat)` `# This code is conteibuted` `# by mohit kumar 29` |

## C#

`// C# Program to print common element in all` `// rows of matrix to another.` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG` `{` `// Specify number of rows and columns` `static` `int` `M = 4;` `static` `int` `N = 5;` `// prints common element in all rows of matrix` `static` `void` `printCommonElements(` `int` `[,]mat)` `{` ` ` `Dictionary<` `int` `, ` `int` `> mp = ` `new` `Dictionary<` `int` `, ` `int` `>();` ` ` ` ` `// initialize 1st row elements with value 1` ` ` `for` `(` `int` `j = 0; j < N; j++)` ` ` `{` ` ` `if` `(!mp.ContainsKey(mat[0, j]))` ` ` `mp.Add(mat[0, j], 1);` ` ` `}` ` ` ` ` `// traverse the matrix` ` ` `for` `(` `int` `i = 1; i < M; i++)` ` ` `{` ` ` `for` `(` `int` `j = 0; j < N; j++)` ` ` `{` ` ` `// If element is present in the map and` ` ` `// is not duplicated in current row.` ` ` `if` `(mp.ContainsKey(mat[i, j])&&` ` ` `(mp[mat[i, j]] != 0 &&` ` ` `mp[mat[i, j]] == i))` ` ` `{` ` ` `// we increment count of the element` ` ` `// in map by 1` ` ` `if` `(mp.ContainsKey(mat[i, j]))` ` ` `{` ` ` `var` `v = mp[mat[i, j]];` ` ` `mp.Remove(mat[i, j]);` ` ` `mp.Add(mat[i, j], i + 1);` ` ` `}` ` ` `else` ` ` `mp.Add(mat[i, j], i + 1);` ` ` `// If this is last row` ` ` `if` `(i == M - 1)` ` ` `Console.Write(mat[i, j] + ` `" "` `);` ` ` `}` ` ` `}` ` ` `}` `}` `// Driver code` `public` `static` `void` `Main(String[] args)` `{` ` ` `int` `[,]mat = {{1, 2, 1, 4, 8},` ` ` `{3, 7, 8, 5, 1},` ` ` `{8, 7, 7, 3, 1},` ` ` `{8, 1, 2, 7, 9}};` ` ` `printCommonElements(mat);` `}` `}` `// This code is contributed by 29AjayKumar` |

## Javascript

`<script>` `// Javascript Program to prints common element in all` `// rows of matrix` ` ` ` ` `// Specify number of rows and columns` ` ` `let M = 4;` ` ` `let N =5;` ` ` ` ` `// prints common element in all rows of matrix` ` ` `function` `printCommonElements(mat)` ` ` `{` ` ` `let mp = ` `new` `Map();` ` ` ` ` `// initialize 1st row elements with value 1` ` ` `for` `(let j = 0; j < N; j++)` ` ` `mp.set(mat[0][j],1);` ` ` ` ` `// traverse the matrix` ` ` `for` `(let i = 1; i < M; i++)` ` ` `{` ` ` `for` `(let j = 0; j < N; j++)` ` ` `{` ` ` `// If element is present in the map and` ` ` `// is not duplicated in current row.` ` ` `if` `(mp.get(mat[i][j]) != ` `null` `&& mp.get(mat[i][j]) == i)` ` ` `{` ` ` `// we increment count of the element` ` ` `// in map by 1` ` ` `mp.set(mat[i][j], i + 1);` ` ` ` ` `// If this is last row` ` ` `if` `(i == M - 1)` ` ` `document.write(mat[i][j] + ` `" "` `);` ` ` `}` ` ` `}` ` ` `}` ` ` `}` ` ` ` ` `// Driver code` ` ` `let mat = [[1, 2, 1, 4, 8],` ` ` `[3, 7, 8, 5, 1],` ` ` `[8, 7, 7, 3, 1],` ` ` `[8, 1, 2, 7, 9]]` ` ` `printCommonElements(mat)` ` ` ` ` `// This code is contributed by unknown2108` `</script>` |

**Output:**

8 1

The time complexity of this solution is O(m * n) and we are doing only one traversal of the matrix.

This article is contributed by **Aditya Goel**. If you like GeeksforGeeks and would like to contribute, you can also write an article and mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.