Last Updated: 11 Dec, 2020
Smallest Common Element
Moderate
You are given a row-wise sorted matrix of size ‘M*N’. Your task is to return the smallest element that is present in all rows.
If no common element exist, return -1.
Example :
If M = 4 and N = 5, and the matrix is:
{ {1, 2, 3, 4, 5},
{2, 3, 4, 5, 6},
{2, 3, 5, 6, 7},
{1, 3, 4, 5, 6} }
For the given matrix, 3 is the possible smallest element that is present in all the rows.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases. Then each test case follows.
The first line of each testcase contains two integers ‘M’ and ‘N’, denoting the number of rows and columns respectively.
The next ‘M’ line contains ‘N’ integers, denoting the elements of the matrix.
For example:
The matrix above contains 3 rows and 4 columns ans will be represented as:
4 3
1 2 3 4
4 6 7 8
9 10 11 12
Output Format :
For each test case print a single integer denoting the smallest common element.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 10
1 <= M,N <= 100
0 <= matrix[i][j] <= 10^9
Time limit: 1 sec
Sample Input 1 :
2
2 3
1 2 3
2 3 6
1 5
1 2 3 4 5
Sample Output 1 :
2
1
Explanation For Sample Output 1 :
For test case 1 :
The given grid is:
2 is the smallest element present in both 1st and 2nd row.
For test case 2 :
The given grid is:
As there is only a single row, so the smallest element in that row will be the smallest common element.
Sample Input 2 :
2
2 2
10 20
30 40
1 1
5
Sample Output 2 :
-1
5
Approaches
Iterate elements of the first-row one by one, and for each element check if it is present in each row.
The steps are as follows:
- Iterate elements of the first row.
- For each element of the first row, iterate the remaining M - 1 rows and linearly search the element.
- If the element is not present in some row then move to the next element of the first row and repeat step 2.
- Return the element currently being searched if present in all rows, This is the smallest common element.
- If you reach the end of the first row, return -1.
Iterate elements of the first-row one by one, and for each element check if it is present in each row using binary search.
The steps are as follows:
- Iterate elements of the first row.
- For each element of the first row, iterate the remaining M-1 rows and search the element in each row using binary search.
- If the element is not present in some row then move to the next element of the first row and repeat step 2.
- Return the element currently being searched if present in all rows, This is the smallest common element.
- If you reach the end of the first row, return -1.
Create a hash map with elements of the first row, set the value of each key to 1 in the hash map. Now iterate the remaining elements of M-1 rows, if the element is present in the hash map then increment the value corresponding to it, but remember not to double count, to take care of this ignore the element if it’s equal to the previous element of that row.
Finally, the hash map will store the count of row-wise occurrences. To get the smallest answer, iterate through the elements of the first row, and check the value corresponding to it in the hash map if the value is equal to the number of rows.
Note: We could have created a hash map of all the elements of the matrix, but that would have a very high space complexity. And we tackled it by just considering the elements of the first row in our hash map, as we are if an answer exists it must be an element of the first row also.
The steps are as follows:
- Iterate elements of the first row and create a hash map with each value corresponding to each element initialized to 1.
- Iterate the elements of the remaining M-1 rows, for each element check that it is not equal to the previous element, and then search the element in hash_map.
- If the element is found in the hash map then increase the value corresponding to the element in the hash map.
- Finally iterate through the elements of the first row.
- If the value corresponding to the element is equal to M, return the element.
- If you reach the end of the first row, return -1.