Kth Smallest in Sorted Matrix

Find the kth smallest element in an n x n matrix where every row and column is sorted.

matrix binary-search heap arrays

You are given an n x n integer matrix where each row and each column is sorted in ascending order. You are also given a positive integer k (1 <= k <= n*n). Write a function `kth_smallest(matrix, k)` that returns the kth smallest element in the matrix.

The matrix is represented as a list of lists of integers. Each row is sorted in non-decreasing order, and each column is sorted in non-decreasing order. The returned value must be an integer.

Your solution should be efficient enough for n up to 300. Aim for O(n * log(max-min) ) or better.

Constraints

- 1 <= n <= 300 (matrix is square)
- -10^9 <= matrix[i][j] <= 10^9
- 1 <= k <= n*n
- Each row and each column is sorted in non-decreasing order.

Example

>>> kth_smallest([[1,5,9],[10,11,13],[12,13,15]], 8)
13
>>> kth_smallest([[-5]], 1)
-5
>>> kth_smallest([[1,2],[1,3]], 3)
2

40 points ~35 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

The answer lies between the smallest element (top-left) and the largest element (bottom-right).

For a candidate value x, count how many elements are <= x. This count can be computed efficiently in O(n) by starting at the bottom-left corner.

Use binary search on the value range. Find the smallest x such that the count of elements <= x is at least k.

A heap-based approach also works but is O(k log n), which may be slower for large k. The binary search approach is preferred.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.