{ }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

    • The matrix is not fully flattened in sorted order, but rows and columns still give strong structure.
    • That structure is enough to count how many values are below a target without examining every cell from scratch.

  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 also qualifies, so add row + 1 and move right. Otherwise move up.
    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.

  6. Step 6: Final solution and complexity

    Binary-search the value range and count rank in O(n) per probe, for O(n log(value range)) time and constant extra space.

    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
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?