{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Kth Smallest Element in a Sorted Matrix – Solution & Complexity

Interview solutions
/
Kth Smallest Element in a Sorted Matrix

Solution Walkthrough

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. 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. 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. 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. 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. 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)Binary Search solution (easy)Longest Increasing Path in a Matrix solution (hard)Longest Increasing Subsequence solution (hard)Median of Two Sorted Arrays solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?