Last Updated: 17 Dec, 2021
Kth Smallest Element
Moderate
Asked in companies
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.
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.
Approaches
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.
- Iterate num through row
In this approach, we can see that our answer will have exactly K - 1 element smaller than itself.
Therefore we will do a binary search on the possible solution and find the mid and count all the elements in each row smaller or equal to the current mid(upper bound). and if the number of elements less than equal to the current mid are fewer than K, then the current mid could be the solution. We have to find the largest mid such that it is greater than K elements in the matrix.
Algorithm:
- Set left as the first element of the first row of the matrix and set right as the last element of the last row of the matrix.
- While the left is less than right.
- Set mid as left + (right - left) / 2
- Set smallerElements as 0
- Iterate row through mat
- Add the upper bound of mid in the row array.
- If smallerElements is less than K, set left as mid + 1
- Otherwise set right as mid.
- Return left