{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Kth Smallest Element in a Sorted Matrix – Solution & Complexity

Interview solutions
/
Kth Smallest Element in a Sorted Matrix

Solution Walkthrough

  1. Step 1: Separate matrix order from global order

    • Rows and columns are sorted, but the flattened matrix is not: reading [[1,5,9],[10,11,13],[12,13,15]] row by row gives 1, 5, 9, 10, 11, 13, 12, 13, 15, so index k - 1 of that order is not the answer.
    • The kth smallest counts duplicates: the fully sorted order is 1, 5, 9, 10, 11, 12, 13, 13, 15, and k = 7 and k = 8 are both 13.
    • The row and column structure is still enough to count how many values are <= target without examining every cell.

  2. Step 2: Brute-force by flattening and sorting

    • Copy every value into one array, sort it, and read the (k - 1)th index.
    • This is simple and correct, but it spends O(n^2 log n) time and O(n^2) extra space.
    def kth_smallest(matrix, k):
    values = []
    for row in matrix:
        values.extend(row)
    values.sort()
    return values[k - 1]

  3. Step 3: Binary-search the answer value

    • If at least k entries are <= mid, the true answer is at most mid.
    • Otherwise, the answer must be larger than mid.

  4. Step 4: Count values <= mid in linear matrix time

    • Start at the bottom-left corner.
    • When matrix[row][col] <= target, everything above it in that column is smaller or equal (columns are sorted), so add row + 1 and move right. Otherwise move up.

    Scan for target = 12 on [[1,5,9],[10,11,13],[12,13,15]] (cells marked * are counted):

            c0    c1    c2
r0  [   1*,   5*,   9* ]
r1  [  10*,  11*,  13  ]
r2  [  12*,  13 ,  15  ]
    cellvaluecompareactioncount
    (r2, c0)12<= 12add 2 + 1 = 3 (1, 10, 12), move right3
    (r2, c1)13> 12move up3
    (r1, c1)11<= 12add 1 + 1 = 2 (5, 11), move right5
    (r1, c2)13> 12move up5
    (r0, c2)9<= 12add 0 + 1 = 1 (9), move right6

    The column index leaves the matrix, so count(<= 12) = 6: exactly 1, 5, 9, 10, 11, 12. This is the mid = 12 row of the binary-search trace below.

    Why up and right are enough

    • Accepted cell: the cells above it in the same column are all <= target, so that column is finished; move right.
    • Rejected cell: every cell to its right in that row is larger (rows are sorted), and rows below it were already rejected in earlier columns, so the current row contributes nothing more; move up.
    • Each move either decreases row or increases col, so a probe takes at most 2n - 1 moves: O(n) time per probe.
    • Duplicates need no special handling: each copy is a separate cell and is counted by <=.
    def kth_smallest(matrix, k):
    def count_less_equal(target):
        n = len(matrix)
        row = n - 1
        col = 0
        count = 0
        while row >= 0 and col < n:
            if matrix[row][col] <= target:
                count += row + 1
                col += 1
            else:
                row -= 1
        return count

    low = matrix[0][0]
    high = matrix[-1][-1]
    while low < high:
        mid = low + (high - low) // 2
        if count_less_equal(mid) < k:
            low = mid + 1
        else:
            high = mid
    return low

  5. Step 5: Dry run / binary-search trace

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

    lowhighmidcount of values <= middecision
    11582need larger values, so low = 9
    915126still too few, so low = 13
    1315148enough values, so high = 14
    1314138enough values, so high = 13

    When low meets high, that value is the smallest number whose rank is at least k. It is always a value in the matrix, because the count only changes at matrix values. Duplicates are why count(13) = 8 jumps from count(12) = 6: both 13s occupy ranks 7 and 8.

  6. Step 6: Final solution and complexity

    Binary-search the value range [min, max] = [matrix[0][0], matrix[n-1][n-1]] and count rank in O(n) per probe. That is O(log(max - min)) probes, for O(n log(max - min)) time and constant extra space. The search is over values, not over the n^2 flattened positions, which are not in sorted order.

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

    low = matrix[0][0]
    high = matrix[-1][-1]
    while low < high:
        mid = low + (high - low) // 2
        if count_less_equal(mid) < k:
            low = mid + 1
        else:
            high = mid
    return low

FAQ

See also

Practice Kth Smallest Element in a Sorted Matrix online (run code in the browser)Search a 2D Matrix solution (medium)01 Matrix solution (medium)Binary Search solution (easy)Find Minimum in Rotated Sorted Array solution (medium)All coding interview problems