MediumArrayBinary SearchMatrix

Kth Smallest Element in a Sorted Matrix

1 approach, code in every language

You are given an n x n grid of integers where each individual row reads in non-decreasing order from left to right, and each individual column reads in non-decreasing order from top to bottom. Note that this ordering guarantee applies within rows and within columns, not across the flattened grid as a whole.

Given a value k, return the k-th smallest number when all of the grid's entries are considered together. Duplicate values count as distinct positions, so the k-th smallest refers to the k-th entry in sorted order, not the k-th unique value.

Example 1

Input: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8

Output: 13

Sorted, the entries are 1, 5, 9, 10, 11, 12, 13, 13, 15. The eighth value in that order is 13.

Example 2

Input: matrix = [[-5]], k = 1

Output: -5

The grid holds a single value, so the first smallest element is that value.

Constraints

n == matrix.length == matrix[i].length
1 <= n <= 300
-10^9 <= matrix[i][j] <= 10^9
1 <= k <= n^2

Binary Search on the Value Range

Binary search over the numeric range and count how many entries are less than or equal to each guess to locate the k-th smallest.

Loading animation…

Intuition

Instead of sorting or scanning entries directly, guess a value and ask how many grid entries do not exceed it. Because both rows and columns are sorted, that count can be gathered in linear time with a staircase walk that starts at the bottom-left corner: moving right adds a whole column prefix, moving up skips values that are too large. The count of entries at or below a guess never decreases as the guess grows, so we binary search for the smallest value whose count reaches k. That value is guaranteed to be an actual grid entry.

Algorithm walkthrough

1Set lo to the top-left entry (the global minimum) and hi to the bottom-right entry (the global maximum).
2Pick mid between lo and hi and count entries less than or equal to mid.
3Do the counting with a pointer at the bottom-left: if the current entry is at most mid, add the whole column above it and move right; otherwise move up.
4If the count is at least k, the answer is at most mid, so set hi = mid; otherwise set lo = mid + 1.
5When lo equals hi, that value is the k-th smallest element.

Implementation

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)

        def countLessEqual(target: int) -> int:
            count = 0
            row, col = n - 1, 0
            while row >= 0 and col < n:
                if matrix[row][col] <= target:
                    count += row + 1
                    col += 1
                else:
                    row -= 1
            return count

        lo, hi = matrix[0][0], matrix[n - 1][n - 1]
        while lo < hi:
            mid = (lo + hi) // 2
            if countLessEqual(mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

Time

O(n log(hi - lo)) where hi and lo are the max and min entries

Space

O(1)

Each count is an O(n) staircase walk; binary search runs about log of the value range iterations.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Priority Queues

After the pattern

Now solve one you haven't seen.

Kth Smallest Drift Reading is our own problem on the technique behind Kth Smallest Element in a Sorted Matrix: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free