K-th Smallest

Easy
0/40
Average time to solve is 15m
34 upvotes
Asked in company
Amdocs

Problem statement

You are given an N x M matrix ‘MAT’ and an integer ‘K’. All rows in the matrix have values in sorted order. You can choose 1 integer from each row and make an array of length ‘N’. Your task is to find the smallest k-th smallest array sum out of all the possibilities.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains ‘T’ denoting the number of test cases.

In the first line of each test case take three space-separated integers,  ‘N’, ‘M’, and ‘K’.

Next N lines contains M space-separated integers MAT[i][j], denoting value stored in position (i, j) in matrix.
Output Format: 
For each test case, print a single line containing a single integer denoting the k-th smallest array sum.

The output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 5
1 <= N, M <= 100
1 <= K <= min(100,N ^ 2)
0 <= MAT[ i ][ j ] <= 2000
MAT[ i ][ j ] <= MAT[ i ][ j + 1 ]

Time Limit: 1 sec.
Sample Input 1:
2
2 3 1
1 2 3
4 5 6
2 3 4
1 2 3
4 5 6
Sample Output 1:
5
7
Explanation for Sample Input 1:
All possible sums in ascending order are:
[ 1 + 4, 1 + 5, 2 + 4, 1+6, 2 + 5, 3 + 4, 2 + 6, 3 + 5, 3 + 6 ]
Sums = [5, 6, 6, 7, 7, 7, 8, 8, 9]

In test case 1:
Ans = sums[1] = 5

In test case 2:
Ans = sums[4] = 7
Sample Input 2:
2
5 5 20
5 6 10 17 29 
8 14 14 21 24 
2 4 23 24 29 
3 4 11 18 24 
0 6 6 15 21 
4 4 11
0 7 7 14 
1 1 7 15 
0 15 18 28 
18 19 24 30
Sample Output 2:
25
26
Hint

Find the K'th smallest sums for each row.

Approaches (1)
Brute Force
  • Let’s first think if in the problem we only had a 2xM matrix, how would we solve the problem.
  • We can find all possible sums in O(M^2) time. Then return the Kth smallest sum after sorting it.
  • So in this problem, we can do the same. We can always take the first two rows then find the sums using  O(M^2) time and only take ‘K’ smallest sums out of them.
  • Then in the next row, we can use these ‘K’ smallest sums and current row, to find all possible sums and again store the ‘K’ smallest sums out of all possibilities.
  • In each row we are doing O(M*K) operations i.e. time complexity will be O(N*M*K).
  • After doing this for all the rows we can just return the ‘K’th smallest sum.

 

Algorithm:

 

  • If there is only one row, we just return the ‘K’th element in the first row as the rows in the matrix are sorted.
  • We create a function sums() which takes two lists as a parameter and returns a list of ‘K’ smallest sums possible (sometimes ‘K’ smallest some is not possible, in that case, we just return the all possible sums).
  • We create a list ‘ans’ = sums( mat[0], mat[1] ), i.e. we find the ‘K’ smallest sums of the first two rows first.
  • Then for each row from mat[2]…mat[n-1], we just update ans= sums(ans, mat[i]).
  • After doing this for all rows we return ‘K’th smallest element in ‘ans’ list.
Time Complexity

O(N * M * K),  where N, M, and K are as described in the problem.

 

 

From every cell in the matrix, we are calculating sums by using K smallest sums till the last row, which makes complexity O(N * M * K)

Space Complexity

O(M * K), where M and K are as described in the problem.

 

 

The size of the ‘cur’ array can go up to M * K, as total sums in the current row can be (K sums from the previous row) * (M possibilities from current row) i.e. O(M * K)

Code Solution
(100% EXP penalty)
K-th Smallest
Full screen
Console