Kth Smallest in a Sorted Matrix

35 min · kthSmallest()

The values are sorted in two directions, but the answer may be buried in the middle of both. You can still find it without sorting all n² cells.

You're given an n x n matrix whose rows and columns are in non-decreasing order, meaning values may rise or stay equal as you move forward. Return the k-th smallest value across every cell, where k is 1-indexed.

Duplicates count by position. If the value 6 occupies three cells, it takes three places in the sorted order.

A few ground rules:

The matrix is square and contains at least one cell.
Both row order and column order matter.
Return the value, not its coordinates.

Constraints

1 <= n <= 300
-1_000_000_000 <= matrix[row][col] <= 1_000_000_000
1 <= k <= n * n
Every row and every column is sorted in non-decreasing order.

Hints

Search values, not positions

The answer lies between the top-left and bottom-right values. For a candidate value, ask how many cells are less than or equal to it.

Count from a corner

Start at the bottom-left cell. If it is at most the candidate, every cell above it in that column also counts. Add them all and move right. Otherwise, move up.

Find the first value with enough cells

If fewer than k cells are at most middle, the answer is larger. Otherwise, middle may already be the answer, so keep it as the upper bound.

Follow-up

If you needed many different k queries for the same matrix, when might paying once to flatten and sort become worthwhile?

Visible cases

Examples

Example 1

ready

Input: matrix = [ [ 1, 4, 8 ], [ 3, 7, 10 ], [ 6, 9, 14 ] ] k = 5
Expected: 7
Why: 7 is fifth after all nine cells are ordered

Example 2

ready

Input: matrix = [ [ 1, 2, 2 ], [ 2, 3, 4 ], [ 3, 4, 5 ] ] k = 4
Expected: 2
Why: three separate cells containing 2 occupy three positions

Example 3

ready

Input: matrix = [ [ -5, -2 ], [ 0, 3 ] ] k = 1
Expected: -5
Why: k = 1 asks for the top-left minimum

Interview signal

Asked at

AmazonGoogleMicrosoft

Flatten + sort

Copy every cell into one list, sort it numerically, and read index k - 1.

def kth_smallest(matrix: list[list[int]], k: int) -> int:
    values = [value for row in matrix for value in row]
    values.sort()
    return values[k - 1]

Time O(n² log(n²)). Space O(n²). This is a clear oracle, but it throws away the matrix's existing row and column order.

Binary search the value

Search the value range from matrix[0][0] to matrix[n - 1][n - 1]. For each candidate middle, count cells <= middle with a staircase walk from the bottom-left corner:

If the current cell is <= middle, every cell above it in that column qualifies too. Add row + 1 and move right.
If it is too large, move up.

def kth_smallest(matrix: list[list[int]], k: int) -> int:
    n = len(matrix)
 
    def count_at_most(limit: int) -> int:
        row, column = n - 1, 0
        count = 0
        while row >= 0 and column < n:
            if matrix[row][column] <= limit:
                count += row + 1
                column += 1
            else:
                row -= 1
        return count
 
    left, right = matrix[0][0], matrix[-1][-1]
    while left < right:
        middle = left + (right - left) // 2
        if count_at_most(middle) < k:
            left = middle + 1
        else:
            right = middle
    return left

The first value with at least k cells beneath it in sorted order is the k-th value. This remains true with duplicates because the count includes every occupied cell.

Time O(n log range). Space O(1). Each count takes at most 2n staircase moves, and binary search spans the numeric range.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arraymatrix: int[][] · k: int

Expected

Run: visible + custom · Submit: full suite