LeetCode #378 Medium

Kth Smallest Element in a Sorted Matrix

Find the kth smallest value in a matrix where only rows and columns are individually sorted.

heapbinary-searchmatrix

02

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.

03

Approach

1

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.

2

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.

3

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.

04

Solution & live demo

python

▶1import heapq
▶2 
▶3class Solution:
▶4    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
▶5        n = len(matrix)
▶6        heap = [(matrix[r][0], r, 0) for r in range(n)]
▶7        heapq.heapify(heap)
▶8        val = None
▶9        for _ in range(k):
▶10            val, r, c = heapq.heappop(heap)
▶11            if c + 1 < len(matrix[r]):
▶12                heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
▶13        return val

05

Edge cases

1x1 matrix

the single element is both the heap seed and the only possible answer for any valid k

k equals total number of elements

the loop pops every element exactly once, ending on the matrix maximum

duplicate values across rows

duplicates are treated as distinct heap entries and counted separately toward k

n x n matrix where n is large

the heap never holds more than n entries at once, which is what keeps this cheaper than flattening and sorting everything

06

Complexity

Time

O(k log n)

Space

O(n)

n is the matrix dimension; the heap never holds more than n entries, one per row.