Kth smallest element in a row- and column-sorted matrix

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}