Medium · Heap Merge of Rows
Understand → Visualise → Practice.
Rows and columns are sorted. Return the kth smallest matrix value, counting duplicates.
Each row is sorted, so the smallest unvisited value is at the front of some row. Pop from a min-heap of row fronts k times.
Push the first value of every row with its (row, column).
Pop the smallest; push the next value in that row if there is one.
The kth value popped is the answer.
O(k log r) time and O(r) space for r rows. (Binary search on the value range is an O(n log V) alternative.)
Flattening and sorting the whole matrix ignores the sorted structure and costs O(n² log n).
Read the full guide first: Heaps and Priority Queues.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.