Workspace

Problem workspace

3 day streakD

Kth Smallest in a Sorted Matrix

MediumBinary SearchNumbers & matrices

The challenge

Return the kth smallest matrix entry, counting duplicate values separately.

Nonempty rectangular matrix; rows AND columns sorted nondecreasingly. 1 ≤ k ≤ r*c; entries are signed 32-bit integers.

Example

[[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8 → 13.

Use the walkthrough below to inspect the input and each state change.

See Matrix value search, step by step

Inspect the comparison, the invariant, and the next boundary.

Answer-space searchk = 8
left1candidate—right15Search candidate values, not input indices
Matrix · row and column indices start at 0 · highlighted entries are ≤ the tested candidate
r / c012
0159
1101113
2121315
Tested candidate / qualifying inputResolved positionParameters shown above
Left
1
Middle
—
Right
15
Step 01 / 6

Search the answer range

The candidate is a number, rather than an input index. Keep the smallest feasible value.

left = 1; right = 15

Recorded result so far

Not resolved
View exact input

Matrix: [[1,5,9],[10,11,13],[12,13,15]] · k = 8

Put it into code

Search values rather than indices. For a candidate mid, count entries ≤ mid using a staircase from the bottom-left.

Indices are zero-based. C++ uses C++17 or later.

def kth_smallest_matrix(matrix, k):
    # Nonempty rectangular matrix, rows AND columns sorted; 1 <= k <= r*c.
    rows, cols = len(matrix), len(matrix[0])
    left, right = matrix[0][0], matrix[-1][-1]
    while left < right:
        mid = left + (right - left) // 2
        row, col, count = rows - 1, 0, 0
        while row >= 0 and col < cols:
            if matrix[row][col] <= mid:
                count += row + 1
                col += 1
            else:
                row -= 1
        if count < k:
            left = mid + 1
        else:
            right = mid
    return left

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap