The kth smallest in a sorted grid
Find the kth smallest value in a grid whose rows and columns are sorted, by expanding outward from the top-left corner with a min-heap. About 16 minutes.
Rows are sorted lists
In this grid every row is sorted from left to right and every column is sorted from top to bottom. So each row is a sorted list, and you can merge the rows as in the last step, without building the merged list.
Put the first value of each row in a min-heap, with its row and column. The smallest value in the whole grid is the top.
heap = [(row[0], r, 0)
for r, row in enumerate(rows)]The heap holds the fronts 1, 10 and 12. Pop 1 (the 1st) and push 5.
Pop k minus 1 times
Pop the smallest entry k minus 1 times. Each time, push the next value in the same row, if there is one. After these pops, the k minus 1 smallest values are gone, so the top of the heap is the kth smallest.
Only the first k rows can matter, because the column order means row k plus 1 starts with something at least as big as k values above it. That keeps the heap small when k is small.
for _ in range(k - 1):
heapq.heappop(h)After popping an entry from a row, what is pushed?
- AThe next value in the same row, if there is one
- BThe value just below it in the next row
- CNothing
Show the answer
The next value in the same row, if there is one. It becomes that row's new front.
Kth smallest element in a sorted matrix
Given an n by n matrix in which each row and each column is sorted in non-decreasing order, and an integer k, return the kth smallest element in the matrix, counted in sorted order, so equal elements count separately. It is guaranteed that 1 ≤ k ≤ n².
matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8 → 13
1 ≤ n ≤ 300 · -1,000,000 ≤ matrix[i][j] ≤ 1,000,000 · 1 ≤ k ≤ n²