Kth Smallest Element in a Sorted Matrix
Last Updated: March 29, 2026
Understanding the Problem
We have a square matrix where each row is sorted left to right and each column is sorted top to bottom. We need to find the kth smallest element overall. The tricky part is that while rows and columns are individually sorted, elements across different rows can interleave. For instance, the last element of row 0 might be larger than the first element of row 2.
The key observation is that the matrix has a special structure: matrix[0][0] is always the global minimum and matrix[n-1][n-1] is always the global maximum. Every path moving right or down encounters non-decreasing values. This structure is similar to merging multiple sorted lists, and it also lends itself to binary search on the answer value.
Key Constraints:
1 <= n <= 300→ The matrix has at most 90,000 elements. O(n^2 log n) is about 1.5 million operations, which is comfortable. But the problem asks for better than O(n^2) memory.-10^9 <= matrix[i][j] <= 10^9→ Values span a huge range, but binary search between matrix[0][0] and matrix[n-1][n-1] handles this efficiently.All rows and columns sorted→ We can treat each row as a sorted list for heap merging, and count elements <= a value in O(n) time using staircase traversal.
Approach 1: Sort All Elements
Intuition
The simplest approach: dump every element into a flat list, sort it, and pick the (k-1)th element. This completely ignores the sorted structure of the matrix, but it's the most obvious starting point and guaranteed to be correct.
Algorithm
- Create an empty list.
- Iterate through every element in the matrix and add it to the list.
- Sort the list.
- Return the element at index
k - 1.
Example Walkthrough
Code
- Time Complexity: O(n^2 log n). We flatten all n^2 elements and sort them. Sorting dominates at O(n^2 log(n^2)) = O(n^2 log n).
- Space Complexity: O(n^2). We store all n^2 elements in a separate list.
This approach works but ignores the sorted structure entirely and uses O(n^2) memory. Since each row is already sorted, what if we treated this as merging k sorted lists with a min-heap?
Approach 2: Min-Heap (Merge K Sorted Rows)
Intuition
Think of the matrix as n sorted lists (one per row). Finding the kth smallest across n sorted lists is a classic problem: use a min-heap. Start by pushing the first element of every row into the heap. Then extract the minimum k times. Each time you extract an element from row i, push the next element in that row (if it exists).
This is the exact same technique used in "Merge K Sorted Lists" (LeetCode #23). The heap always contains at most n elements (one per row), so each push/pop is O(log n). We do this k times, giving us O(k log n).
The heap always contains the smallest unprocessed element from each active row. When we pop the global minimum, we know nothing smaller remains unprocessed, because every row's smallest remaining element is in the heap. By pushing the next element from the same row, we maintain this invariant. After k pops, we've found the kth smallest element.
This is essentially a k-way merge. Instead of merging all n rows completely, we stop after k extractions.
Algorithm
- Create a min-heap. Push the first element of each row as a tuple:
(value, row, col). - Repeat k times:
- Pop the smallest element from the heap.
- If the popped element has a next element in its row (col + 1 < n), push that next element.
- The kth popped element is the answer.
Example Walkthrough
Code
- Time Complexity: O(k log n). We initialize the heap with n elements, then perform k extract-and-insert operations, each costing O(log n).
- Space Complexity: O(n). The heap holds at most n elements at any time (one per row).
The heap approach works well but depends on k. When k is close to n^2, we do nearly n^2 heap operations. What if we binary searched on the answer value instead, leveraging both row and column sorting?
Approach 3: Binary Search on Value
Intuition
Instead of finding the kth element by extracting elements in order, we binary search on what the answer value could be. The search space is the range [matrix[0][0], matrix[n-1][n-1]], the smallest to largest values in the matrix.
For a candidate value mid, we count how many elements in the matrix are <= mid. If the count is >= k, the answer is mid or something smaller, so we search left. If the count < k, we need a larger value, so we search right.
The counting step is where the sorted structure really shines. Starting from the bottom-left corner of the matrix, if the current element is <= mid, the entire column above it (including itself) is also <= mid (because the column is sorted). So we add row + 1 to the count and move right. If the current element is > mid, we move up. This staircase traversal counts all elements <= mid in O(n) time.
Algorithm
- Set
low = matrix[0][0]andhigh = matrix[n-1][n-1]. - While
low < high: - Compute
mid = low + (high - low) / 2. - Count how many elements are <= mid using the staircase traversal.
- If count >= k, set
high = mid(answer could be mid or smaller). - If count < k, set
low = mid + 1(answer must be larger). - Return
low.
Example Walkthrough
Code
- Time Complexity: O(n * log(max - min)). The binary search runs O(log(max - min)) iterations. Each iteration does a staircase count in O(n). With values up to 10^9, log(max - min) is at most ~63.
- Space Complexity: O(1). Only a handful of integer variables. No extra data structures.