Common Elements Present In All Rows Of Matrix

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
58 upvotes
Asked in companies
AmazonCj DARCL logisticsMediaTek

Problem statement

You are given a 2-D Matrix 'MAT' having 'N' rows and 'M' columns, respectively. Your task is to find all elements which are present in each row of the matrix.

Note : 
1. The output array can contain the elements in any particular order.

2. Even if a particular element appears more than once in each matrix row, it should still be present only once in the output array.
For Example : 
Consider the matrix MAT [ [ 2, 3, 4, 7 ] , [ 0, 0, 3, 5 ] , [ 1, 3, 8, 9 ] ] having 3 rows and 4 columns respectively.
The output array should be [ 3 ] as 3 is the only element that is present in all three rows.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains an integer, 'T', denoting the number of test cases.

The first line of each test case contains two space-separated integers, 'N' and 'M', denoting the number of rows and columns in the Matrix 'MAT', respectively.

Each of the next 'N' lines contains 'M' space-separated integers denoting the matrix 'MAT' elements.
Output Format : 
The only line of output of each test case should contain all elements which are present in each row of the given matrix separated by a single space.

Print the output of each test case in a new line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N, M <= 1000
0 <= MAT[i][j] <= 10^9

Where 'MAT[i][j]' denotes the element present at the 'i-th' row and the 'j-th' column of the matrix 'MAT'.

Time Limit: 1 sec
Sample Input 1 :
2
3 4
1 4 5 6
3 4 5 6
5 6 7 2
3 2
4 6 
6 4
2 6
Sample Output 1 :
5 6
6
Explanation for Sample Input 1 :
For the first test case : 
Elements that are common in the first two rows are 4, 5, and 6. Out of which only 5 and 6 are present in the third row. Therefore the output array is [ 5, 6 ] in this case.

For the second test case : 
We can see that only 6 are present in all three rows. Therefore the output array is [ 6 ] in this case.
Sample Input 2 :
2
4 3
1 2 3
2 2 3
2 3 1
2 3 4
3 3
1 2 3
0 6 0
4 6 1
Sample Output 2 :
2 3
Explanation for Sample Input 2 :
For the first test case : 
As elements 2 and 3 are present in all three rows of the matrix. Therefore the output array is [ 2, 3 ] in this case.

For the second test case : 
There is no such element that is present in all three rows. Therefore the output array is an empty array in this case.
Hint

Iterate through the first row and try to check for each element whether it is present in all the other rows or not

Approaches (3)
Brute Force Approach

The idea is to iterate through the first row, and for each element of the row, iterate through all the other rows and check whether that element is present in them. If that element exists in all the other rows, we will add it to the output array. In the end, we will return the output array after removing duplicates.

 

Algorithm

 

  • Iterate from k = 0 to M-1
    • If MAT[0][k] is already present in the output array, then we will ignore the current element and move ahead to the next element of the first array.
    • Define a flag isPresentInAllRows to store whether an element is present in all rows. Initialise it as 1.
    • Iterate from i = 1 to N-1
      • Define a flag variable isPresentInCurrentRow to check whether the element is present in the current row. Initialise it as 0.
      • Iterate from j = 0 to M-1 
        • If MAT[0][k] equals MAT[i][j] then set isPresentInCurrentRow to 1 and break the loop.
      • If isPresentInCurrent Row is equal to 0, then set isPresentInAllRows as 0 and break the loop.
    • If the flag variables isPresentInAllRows is set to 1, we will add MAT[0][k] to the output array.
  • Return the output array.
Time Complexity

O(N*(M^2)), where ‘N’ and ‘M’ are the number of rows and columns in the Matrix, respectively. 

 

In the worst case, For each of the M elements of the first row, we will need to traverse the N-1 rows and M columns of the matrix. Hence, the overall Time Complexity is O(N*(M^2)).

Space Complexity

O(1).

 

We are using constant extra space only. Hence, the overall Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Common Elements Present In All Rows Of Matrix
Full screen
Console