Kth Smallest Element

Moderate

0/80

Contributed by

5 upvotes

Asked in companies

Problem statement

You are given a square matrix ‘NxN’ rows and columns. The matrix is sorted, meaning all rows and columns of the matrix are sorted in ascending order. You are also given an integer ‘K’, and your task is to find the ‘K’th smallest element in the sorted order.

For example:

You are given ‘mat’ = [[1, 2, 2,], [3, 3, 4], [5, 6 ,7]]] and ‘K’ = 5, the elements of the matrix are [1, 2, 2, 3, 3, 4, 5, 6, 7], the 5th smallest element in the matrix is 3. Hence the answer is 3.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a single integer ‘T’ representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, representing the order of the square matrix given and the integer given.

The following ‘N’ lines contain ‘N’ space-separated integers representing a row of the matrix.

Output Format:

For each test case, print a single integer representing the ‘K’ the smallest element in the sorted matrix.

Constraints:

1 <= T <= 10
1 <= N <= 10^3
1 <= |mat[i][j]| <= 10^4

Time Limit: 1 sec

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Sample Input 1:

Sample Output 2:

3
2

Explanation:

For the first test case, ‘mat’ = [[1, 2, 2,], [3, 3, 4], [5, 6 ,7]]] and ‘K’ = 5, the elements of the matrix are [1, 2, 2, 3, 3, 4, 5, 6, 7], the 5th smallest element in the matrix is 3. Hence the answer is 3.

For the second test case,  ‘mat’ = [[1, 2], [3, 4]] and ‘K’ = 2, the elements of the matrix are [1, 2, 3, 4], the 2nd smallest element in the matrix is 2. Hence the answer is 2.

Sample Input 2:

Sample Output 2:

1
2

Hint 1

Hint 2

Which data structure can give the maximum of K elements

Approaches (2)

Approach 1

Approach 2

Heap

In this approach, we iterate all elements in the matrix and add elements into the maxHeap. The maxHeap will keep up to k smallest elements (because when maxHeap is over the size of k, we do remove the top of maxHeap, which is the largest one). Finally, the top of the maxHeap is the kth smallest element in the matrix.

Algorithm:

Set elementIndex as 0.
Iterate row through mat
- Iterate num through row
  - If elementIndex is equal to K, return num
  - Increase elementIndex by 1.

Time Complexity

O((N^2)* log(K)), Where N and K are the order of the matrix and the integer given.

We are using a heap of K elements. So each operation will cost O(log(K)), and in the worst case, we will perform O(N^2) operations. Hence the overall time complexity O((N^2)*log(K))

Space Complexity

O(K), Where K is the integer given.

We are maintaining a heap of K elements. Hence the space complexity is O(K).

(100% EXP penalty)

Kth Smallest Element

Console