Kth smallest element in a row- and column-sorted matrix
Problem
Every row and every column of an n × n matrix is sorted in ascending order. Return the kth smallest element overall, counting duplicates.
Example 1
Input: matrix = [[1,5,9], [10,11,13], [12,13,15]], k = 8 Output: 13
Also asked as: Kth smallest element in a row-cpumn wise sorted matrix
Test cases
Case 1
Input: [[1,5,9],[10,11,13],[12,13,15]], 8 Expected: 13
Case 2
Input: [[-5]], 1 Expected: -5
Case 3
Input: [[1,2],[1,3]], 2 Expected: 1
View solutionHide solution1 approach
1. Binary search on the value
Time O(n · log(range))Space O(1)
Count cells ≤ mid with a staircase walk (O(n)). The answer is the smallest value whose count ≥ k.
function kthSmallest(m, k) { const n = m.length; let lo = m[0][0], hi = m[n - 1][n - 1]; const countLE = (x) => { let cnt = 0, r = n - 1, c = 0; while (r >= 0 && c < n) { if (m[r][c] <= x) { cnt += r + 1; c++; } else r--; } return cnt; }; while (lo < hi) { const mid = lo + ((hi - lo) >> 1); countLE(mid) < k ? (lo = mid + 1) : (hi = mid); } return lo;}