Kth Smallest in a Sorted Matrix
MediumBinary search the value, count what is below
Problem
Given an n x n matrix where each row and each column is sorted in ascending order, return the kth smallest element in the matrix.
Binary-search a value; count cells <= it row by row, narrowing to the k-th smallest.
The idea
Search the value range rather than any index: for a candidate value, count how many matrix entries are at most it using the staircase walk. Shrink the range until the smallest value with a count of at least k remains.
The trick
- Search on values between matrix[0][0] and matrix[n-1][n-1].
- Counting is O(n) per candidate via the staircase, so the total is O(n log range).
- The answer is guaranteed to be a real matrix entry.
Step 1 of 6. 3×3 matrix, median = 5th smallest of 9. Binary search the value. Values: 1, 2, 3, 4, 5, 6, 7, 8, 9. Pointers: lo at index 0, hi at index 8.
Count with per-row upper bound.
1let lo = min, hi = max, need = (rows * cols) / 2;2while (lo < hi) {3 const mid = (lo + hi) >> 1;4 let cnt = 0;5 for (const row of grid) cnt += upperBound(row, mid);6 if (cnt > need) hi = mid;7 else lo = mid + 1;8}9return lo;Input
- array
- [1, 2, 3, 4, 5, 6, 7, 8, 9]
Memory
- lo
- = 0 [1]
- hi
- = 8 [9]
- mid
- —
- count ≤ x
- —
Output
- count ≤ x
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
- Output:
- 13
- Explanation:
- The 8th smallest value is 13.
Example 2
- Input:
- matrix = [[1,2],[1,3]], k = 2
- Output:
- 1
- Explanation:
- Second smallest is 1.
Example 3
- Input:
- matrix = [[5]], k = 1
- Output:
- 5
- Explanation:
- Only element.
Constraints
- 1 <= n <= 300
- 1 <= k <= n*n
- Each row and column is sorted ascending.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.