How To Find The Kth Smallest Element in a Sorted Matrix
Problem statement
You are given an n x n
matrix where each row and column is sorted in ascending order. Your task is to find the kth
smallest element in this matrix.
Please note that we are looking for the kth
smallest element based on its position in the sorted order, and not counting distinct elements.
Additionally, it is required to find a solution with a memory complexity better than O(n^2)
.
Example 1
Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13
Example 2
Input: matrix = [[5]], k = 1
Output: 5
Constraints
n == matrix.length == matrix[i].length
.1 <= n <= 300
.10^9 <= matrix[i][j] <= 10^9
. All the rows and columns of
matrix
are guaranteed to be sorted in nondecreasing order. 1 <= k <= n^2
.
Follow up
 Could you solve the problem with a constant memory (i.e.,
O(1)
memory complexity)?  Could you solve the problem in
O(n)
time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.
Solution 1: Transform the 2D matrix into a 1D vector then sort
You can implement exactly what Example 1 has explained.
Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int kthSmallest(vector<vector<int>>& matrix, int k)
{
vector<int> m;
for (auto& row : matrix)
{
m.insert(m.end(), row.begin(), row.end());
}
sort(m.begin(), m.end());
return m.at(k  1);
}
int main()
{
vector<vector<int>> matrix{{1,5,9},{10,11,13},{12,13,15}};
cout << kthSmallest(matrix, 8) << endl;
matrix = {{5}};
cout << kthSmallest(matrix, 1) << endl;
}
Output:
13
5
Code explanation

To simplify the problem, the code starts by flattening the 2D matrix into a 1D vector named
m
. It does this by iterating through each row of the matrix and appending the elements of each row to the end of them
vector. 
After flattening the matrix, the code uses the
sort
function from the C++ Standard Library to sort them
vector in ascending order. This step ensures that all elements in the vector are in sorted order. 
Finally, the code returns the
k
th smallest element from the sortedm
vector. Since the vector is 0based indexed, thek
th smallest element corresponds to the element at indexk  1
in the sorted vector.
Complexity
The core idea behind this solution is to transform the 2D matrix into a 1D sorted array, making it easier to find the k
th smallest element efficiently. The time complexity of this solution is dominated by the sorting step, which is O(N*logN)
, where N
is the total number of elements in the matrix.
 Runtime:
O(N*logN)
, whereN = n^2
is the total number of elements in the matrix.  Extra space:
O(N)
.
Solution 2: Build the max heap and keep it ungrown
Instead of sorting after building the vector in Solution 1, you can do the other way around. It means building up the vector from scratch and keeping it sorted.
Since you need only the kth
smallest element, std::priority_queue
can be used for this purpose.
Code
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int kthSmallest(vector<vector<int>>& matrix, int k)
{
priority_queue<int> q;
for (int row = 0; row < matrix.size(); row++)
{
for (int col = 0; col < matrix[row].size(); col++)
{
q.push(matrix[row][col]);
if (q.size() > k)
{
q.pop();
}
}
}
return q.top();
}
int main()
{
vector<vector<int>> matrix{{1,5,9},{10,11,13},{12,13,15}};
cout << kthSmallest(matrix, 8) << endl;
matrix = {{5}};
cout << kthSmallest(matrix, 1) << endl;
}
Output:
13
5
Code explanation

The code initializes a
priority_queue
namedq
, which is a minheap. This minheap will be used to keep track of the smallestk
elements encountered in the matrix. 
The code uses two nested loops to iterate through the matrix elements. The outer loop iterates over each row, and the inner loop iterates over each column within the row.

For each element in the matrix (represented by
matrix[row][col]
), the code pushes it into the priority queueq
. This operation effectively adds the element to the heap while maintaining the heap property (smallest element at the top). 
After pushing an element into the priority queue, the code checks if the size of the priority queue
q
exceeds the value ofk
. If it does, it means there are more thank
elements in the priority queue. To ensure that the priority queue contains only the smallestk
elements, the code uses thepop
operation to remove the top (smallest) element from the priority queue. This step keeps the size of the priority queue constant atk
. 
After processing all elements in the matrix, the priority queue
q
will contain the smallestk
elements, with thek
th smallest element at the top of the priority queue. The code returns the top element of the priority queue usingq.top()
, which is thek
th smallest element in the matrix.
Complexity
The key idea behind this solution is to maintain a priority queue of size k
, allowing it to efficiently keep track of the k
th smallest element encountered while iterating through the matrix. This approach is handy for large matrices, as it doesn't require sorting the entire matrix.
 Runtime:
O(N*logk)
, whereN = n^2
is the total number of elements of the matrix.  Extra space:
O(k)
.
Solution 3: Binary search
Since the matrix is somehow sorted, you can perform the binary search algorithm.
But the criteria for the search is not the value of the element x
of interest; it is the number of elements that are less than or equal to x
must be exactly k
. You can use std::upper_bound
for this purpose.
Code
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int countLessOrEqual(const vector<vector<int>>& matrix, int x)
{
int count = 0;
for (const auto& row : matrix)
{
count += upper_bound(row.begin(), row.end(), x)  row.begin();
}
return count;
}
int kthSmallest(vector<vector<int>>& matrix, int k)
{
int left = matrix.front().front();
int right = matrix.back().back();
while (left <= right)
{
int mid = left + (right  left) / 2;
if (countLessOrEqual(matrix, mid) >= k)
{
right = mid  1;
}
else
{
left = mid + 1;
}
}
return left;
}
int main()
{
vector<vector<int>> matrix{{1,5,9},{10,11,13},{12,13,15}};
cout << kthSmallest(matrix, 8) << endl;
matrix = {{5}};
cout << kthSmallest(matrix, 1) << endl;
}
Output:
13
5
Code explanation

The function
countLessOrEqual
counts the number of elements in the matrix that are less than or equal to a given valuex
. It iterates through each row of the matrix.
 For each row, it uses the
upper_bound
function from the C++ Standard Library to find the position of the first element greater thanx
. By subtracting the iterator obtained fromupper_bound
by the beginning of the row, it calculates the count of elements less than or equal tox
in that row and adds it to thecount
.  Finally, it returns the total count.

The function
kthSmallest
finds thek
th smallest element in the matrix using a binary search approach. It initializes two variables,
left
andright
, to represent the minimum and maximum possible values in the matrix.left
is set to the smallest element in the first row, andright
is set to the largest element in the last row.  It enters a binary search loop where it continuously narrows down the search range by calculating the
mid
value as the average ofleft
andright
.  In each iteration, it calls the
countLessOrEqual
function to count how many elements in the matrix are less than or equal tomid
.  If the count is greater than or equal to
k
, it updatesright
tomid  1
, effectively narrowing the search range to the left half.  If the count is less than
k
, it updatesleft
tomid + 1
, narrowing the search range to the right half.  The binary search continues until
left
is greater thanright
, at which point it has found the kth smallest element.  It returns
left
as thek
th smallest element.
 It initializes two variables,
The binary search in the kthSmallest
function efficiently narrows the search range based on the count of elements less than or equal to the midpoint value. This is a highly efficient approach for large matrices.
Complexity

The binary search in the
kthSmallest
function iterates untilleft
is greater thanright
. In each iteration, it calculates themid
value as the average ofleft
andright
. 
In each iteration of the binary search, the
countLessOrEqual
function is called. This function iterates through each row of the matrix and performs anupper_bound
operation on that row. Theupper_bound
operation has a time complexity ofO(logn)
for each row, wheren
is the number of elements in a row. The worstcase time complexity of thecountLessOrEqual
function isO(n*logn)
for a single call. 
In the binary search, the search range is continuously halved with each iteration. Therefore, the number of binary search iterations required to converge to the final answer is
O(log(maxmin))
, wheremax
andmin
are the maximum and minimum possible values in the matrix. 
Combining the above points, the overall time complexity of the
kthSmallest
function isO(log(maxmin)) * O(n*logn)
.
In summary:
 Runtime:
O(n*logn*log(max min))
, wheren
is the number of rows/columns of the matrix,max
andmin
are the maximum and minimum possible values in the matrix..  Extra space:
O(1)
.
If you found this helpful, please share it with a friend and consider subscribing if you haven’t already. Also, if you have feedback about how we can make the content better, please share it here. Thank you very much!