Smallest Common Element

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
5 upvotes

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Hint

The common element must belong to the first row, so the answer if exists must be one of the elements from the first row.

Approaches (3)
Brute Force

 

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:

  1. Iterate elements of the first row.
  2. For each element of the first row, iterate the remaining M - 1 rows and linearly search the element.
  3. If the element is not present in some row then move to the next element of the first row and repeat step 2.
  4. Return the element currently being searched if present in all rows, This is the smallest common element.
  5. If you reach the end of the first row, return -1.
Time Complexity

O( N*M*N ), where M and N are the number of rows and columns respectively.

 

Since there are N elements in the first row, and for each element, we may need to check all the remaining (M-1)*N elements, Hence the time complexity is O(N*M*N).

Space Complexity

O(1)


Since constant space used. Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Smallest Common Element
Full screen
Console