Kth Smallest Element in a Sorted Matrix
Task example: Kth Smallest Element in a Sorted Matrix
Given an n × n matrix whose rows and columns are sorted in nondecreasing order, return its kth smallest value. Count duplicates separately; k is 1-based. The task requires less than O(n²) extra space. Keep the matrix unchanged.
Together the values sort to [1, 5, 9, 10, 11, 12, 13, 13, 15]. The eighth value is 13. Rows and columns are sorted, but reading row by row is not globally sorted: 13 comes before 12.
Flatten and sort: video explanation
matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8 → 13
Prefer reading? Follow the steps below.
- Create an empty values list. Visit each row, then append each value to the list. Copy all n² entries, including duplicates.
- Sort values once, after both loops. Row-by-row order alone is not enough: the next row may start with a smaller value.
- Return values[k - 1]. Rank k starts at 1, while list indices start at 0. For k = 8, index 7 holds 13. This baseline does not satisfy the task’s better-than-O(n²) extra-space requirement.
Time complexity · O(n² log n)
There are n² entries. Copying takes O(n²); sorting them dominates at O(n² log n) for n >= 2. A single-cell matrix takes constant time.
Space complexity · O(n²)
The copied list and Python sorting workspace use O(n²) extra space. The original matrix stays unchanged.
Binary search over values: video explanation
matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8 → 13
Prefer reading? Follow the steps below.
- Search from matrix[0][0] to matrix[-1][-1]. We seek the smallest threshold with at least k entries <= threshold. A threshold need not appear in the matrix.
- For mid = (left + right) // 2, start at the bottom-left cell. If matrix[row][col] <= mid, all cells above it also fit: add row + 1 to count and move right. Otherwise move up. Each count takes at most 2n steps.
- If count >= k, keep mid with right = mid. Otherwise discard it and all smaller thresholds with left = mid + 1. Count repeated entries separately.
- When the bounds meet, return left. In the example, thresholds 8, 12, 14, and 13 give counts 2, 6, 8, and 8. The first threshold reaching k = 8 is 13.
This avoids the baseline’s copied list and meets the memory requirement. It uses row and column order for staircase counting. Running time depends on the value range, so constant space does not mean universally fastest.
Time complexity · O(n log(R + 1))
Let R = matrix[-1][-1] - matrix[0][0] + 1. Each count is O(n), and binary search halves the value range. O(n log(R + 1)) is a worst-case bound; equal bounds return immediately.
Space complexity · O(1)
Only bounds, indices, and a counter are stored: O(1) extra space. No copied list, sorting, or input mutation.