Kth Smallest Element in a Sorted Matrix
Find the kth smallest value in a matrix where only rows and columns are individually sorted.
Open on LeetCode ↗Intuition
The trap is assuming the matrix is globally sorted in row-major order, so the answer would just be index k-1 after flattening. That assumption is false: only each ROW and each COLUMN is individually sorted, and the last element of row 0 can easily exceed the first element of row 1. A min-heap seeded with the first element of every row fixes this -- the true smallest remaining value is always one of the current row heads, because nothing smaller can be hiding further along any row. Pop the smallest head k times, pushing each popped row's next element back in, and the kth pop is the answer.
A k-way merge across the rows. Seed the heap with each row's first element, then popping k times walks the merged order — each pop pushes only the next element from that same row, so the heap never exceeds n entries.
Approach
Seed a heap with the row heads
Push the first element of every row into a min-heap, each tagged with which row it came from and its column index. These are the only candidates that could possibly be the current smallest, since every row is individually sorted.
Pop the smallest k times
Repeat k times: pop the minimum from the heap, and if the row it came from has a next element, push that next element in its place. Each pop advances exactly one row's pointer by one.
The kth pop is the answer
Because the heap always holds the true frontier of unexplored-but-reachable values, the value popped on the kth iteration is guaranteed to be the kth smallest across the whole matrix, without ever assuming a global sort order.
Solution & live demo
Common pitfalls
Pushing the whole matrix into the heap
heap = [v for row in matrix for v in row] heapq.heapify(heap)
heap = [(matrix[r][0], r, 0) for r in range(n)]
That's O(n²) space and discards the row ordering the problem gives you. Seeding one element per row keeps the heap at size n and pulls in the rest lazily.
Not tracking the column index
heapq.heappush(heap, matrix[r][c + 1])
heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
Without the coordinates in the entry, the next pop has no way to know which row to advance. The triple carries the position along with the value.
Popping k + 1 times
for _ in range(k + 1):
for _ in range(k):
The k-th smallest is the value of the k-th pop, since the first pop yields the smallest. One extra iteration returns the (k+1)-th element.
Edge cases
the single element is both the heap seed and the only possible answer for any valid k
the loop pops every element exactly once, ending on the matrix maximum
duplicates are treated as distinct heap entries and counted separately toward k
the heap never holds more than n entries at once, which is what keeps this cheaper than flattening and sorting everything