Last Updated: 5 Apr, 2021

K-th Smallest

Easy

Asked in company

Solve now

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.

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.

Solve now

Approaches

01 Approach

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.

Solve now