The k-th smallest in a sorted table
Find the k-th smallest number in a table with sorted rows and columns by searching the value and counting with a staircase. About 17 minutes.
Count the cells at most x
Here every row and every column is sorted, though one row's end isn't tied to the next row's start. Sorting all the cells would work, but it's wasteful.
Instead ask: for a value x, how many cells are at most x? Stand in the bottom-left corner. If that cell is at most x, so is everything above it in the column, so add the column height and step right. If it is bigger than x, step up. The walk takes at most twice the table's side.
count = 0
for v in row:
if v <= x:
count += 1Values range from 2 to 12. Try 7: 2, 3, 4, 6 and 7 are at most 7, so 5 cells. That reaches 5, so keep 7 and look lower.
Search the value
The k-th smallest is the smallest value x for which at least k cells are at most x. The count only goes up as x goes up, so you can halve the range of values between the smallest cell (the top-left) and the largest (the bottom-right).
If the count at the middle value reaches k, the answer is that value or smaller, so keep it. If not, the answer is larger.
low, high = smallest, biggest # search the values, not positions mid = (low + high) // 2
For a value x you count 5 cells at most x, and you need the 7th smallest. What next?
- ALook at larger values, since 5 is fewer than 7
- BLook at smaller values
- Cx is the answer
Show the answer
Look at larger values, since 5 is fewer than 7. The 7th smallest must be larger than x, because only 5 cells fit under it.
K-th smallest in a sorted table
matrix is a square table of whole numbers in which every row is sorted from left to right and every column is sorted from top to bottom. Return the k-th smallest number in the table, counting repeated numbers separately.
matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8 → 13
1 ≤ side ≤ 300 · −1,000,000,000 ≤ value ≤ 1,000,000,000 · 1 ≤ k ≤ side × side