Kth Smallest Element in a Sorted Matrix

104k
0

Given an N x N matrix where every row and every column is sorted in non-decreasing order, return the kth smallest element in the matrix. The kth smallest element means the element at position k after all matrix values are arranged in sorted order.

Duplicates are counted separately. So if 13 appears twice, both copies take their own positions in sorted order.

Example 1

Input: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8

Output: 13

Explanation: If we list all the elements of the matrix in a single sorted line, they look like [1, 5, 9, 10, 11, 13, 13, 15]. The 8th smallest element in this sorted list is 13.

Example 2

Input: matrix = [[-5]], k = 1

Output: -5

Explanation: The matrix has only one element, so the 1st smallest element is naturally -5.

Brute Force Approach

The most direct idea is to collect every number from the matrix into one list. Once all values are in one list, sorting that list gives the exact order in which the smallest, second smallest, third smallest, and so on appear.

Since k is 1-based, the answer will be at index k - 1 in the sorted list. This approach is very easy to understand because it follows the problem statement directly.

Algorithm

  • Create an empty list to store all matrix values. This is needed because the kth smallest element is based on the full sorted order, not on one row or one column.

  • Traverse every row and every column, and put each value into the list so no element is missed.

  • Sort the list because the kth smallest position only becomes clear after all values are in increasing order.

  • Return the value at index k - 1 because arrays use 0-based indexing, while k is given as a 1-based position.

Dry Run

Kth Smallest Element in a Sorted Matrix Brute Dry Run

Kth Smallest Element in a Sorted Matrix Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the kth smallest value by collecting
all matrix elements and sorting them.
*/
int kthSmallest(vector<vector<int>>& matrix, int k) {
// This stores every matrix value in one simple list.
vector<int> values;
for (int i = 0; i < (int)matrix.size(); i++) {
for (int j = 0; j < (int)matrix[i].size(); j++) {
values.push_back(matrix[i][j]);
}
}
// Sorting gives the exact global order of all values.
sort(values.begin(), values.end());
// k is 1-based, so k - 1 gives the matching 0-based index.
return values[k - 1];
}
};
// Driver code starts
int main() {
vector<vector<int>> matrix = {
{1, 5, 9},
{10, 11, 13},
{12, 13, 15}
};
int k = 8;
Solution obj;
cout << obj.kthSmallest(matrix, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N2 x log(N2)), because all N2 elements are sorted together which gives N2 x log(N2) as the complexity.

Space Complexity: O(N2)because all matrix values are stored in a separate list.

Better Approach

Each row of the matrix is already sorted, so the matrix can be viewed as N sorted arrays.

Finding the kth smallest element can therefore be treated as the problem of merging N sorted arrays and finding the kth element without necessarily storing the complete merged array.
For a better understanding of this approach, refer to this: Merge K Sorted Arrays

A min-heap stores the smallest unprocessed element from each row. The heap always provides the smallest available value. After removing an element from a row, the next element from the same row is inserted because the row is sorted.

Thus, the problem becomes merging N sorted arrays using a min-heap and stopping after reaching the kth element.

Algorithm

  • Put the first element of each row into a min-heap. This is done because the first element is the smallest unused value from that row.

  • Store the value, row index, and column index in the heap so that after removing an element, the next element from the same row can be found.

  • Remove the smallest heap element exactly k - 1 times. This discards the first smallest, second smallest, and so on until the heap top becomes the kth smallest.

  • After removing an element, check whether the same row has a next column. If it exists, push that next value into the heap because it is now the smallest unused value from that row.

  • Return the value at the top of the heap because after k - 1 removals, it represents the kth smallest value.

Dry Run

Kth Smallest Element in Sorted Matrix Optimal Dry Run

Kth Smallest Element in Sorted Matrix Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the kth smallest value by treating
each matrix row like a sorted list.
*/
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
// Each heap entry stores value, row, and column.
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> minHeap;
// Only the first min(n, k) rows can matter at the beginning.
for (int row = 0; row < n && row < k; row++) {
minHeap.push({matrix[row][0], row, 0});
}
// Remove k - 1 smaller values so the heap top becomes the kth value.
for (int removed = 1; removed < k; removed++) {
vector<int> current = minHeap.top();
minHeap.pop();
int row = current[1];
int col = current[2];
// If the same row has a next value, it becomes the next candidate from this row.
if (col + 1 < n) {
minHeap.push({matrix[row][col + 1], row, col + 1});
}
}
// The smallest remaining candidate is now the kth smallest value.
return minHeap.top()[0];
}
};
// Driver code starts
int main() {
vector<vector<int>> matrix = {
{1, 5, 9},
{10, 11, 13},
{12, 13, 15}
};
int k = 8;
Solution obj;
cout << obj.kthSmallest(matrix, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(K × log(min(N, K))), where N is the number of rows/columns and K is the given position.

  • O(min(N, K)) to insert the first element from each relevant row into the min-heap.

  • O(K × log(min(N, K))) to perform K - 1 heap removals and insertions.

So, overall time complexity is O(K × log(min(N, K))).

Space Complexity: O(min(N, K)), N is the number of rows, because the heap stores at most one active candidate from each useful row.

Optimal Approach

The smallest possible answer is the top-left value, and the largest possible answer is the bottom-right value. So instead of binary searching over matrix indexes, the search can happen over the value range.

For any chosen value mid, the next step is to count how many elements are less than or equal to mid. Since every row and column is sorted, this count can be found efficiently without checking every element.

Start from the bottom-left corner:

  • If matrix[row][col] <= mid, every element above it in the same column is also <= mid. So row + 1 elements can be counted at once, then move right.

  • If matrix[row][col] > mid, the current value and the values below it are too large. Move up to find smaller values.

For a detailed explanation of bottom-left matrix traversal, refer to this :- Search in 2D Matrix 2

After getting the count:

  • If count >= k, the kth smallest value is mid or smaller, so move the search range left.

  • If count < k, mid is too small, so move the search range right.

This binary search continues until low == high, which gives the kth smallest value.

Algorithm

  • Set low to the smallest matrix value and high to the largest matrix value. This creates the range where the final answer must exist.

  • Find the middle value of the current range. This value is not a matrix index; it is a possible answer.

  • Count Elements <= mid: Start at the bottom-left corner (row = N - 1, col = 0) with count = 0:

  • While row >= 0 and col < M:

    • If matrix[row][col] <= mid, add row + 1 to count and increment col by 1.

    • Else (matrix[row][col] > mid), decrement row by 1.

  • If the count is at least k, move high to mid because the kth smallest value can be mid or smaller.

  • Otherwise, move low to mid + 1 because not enough values are less than or equal to mid, so the answer must be larger.

  • When low and high meet, return that value because it is the smallest value that has at least k elements less than or equal to it.

Key Points

  • Duplicates are counted separately, which is why the condition uses count >= k also The count step must use <= mid, not < mid, because duplicates can be part of the kth position.

  • Negative numbers work naturally because the search range starts from matrix[0][0] and ends at matrix[n - 1][n - 1].

Dry Run

Optimal

Optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
int countLessEqual(vector<vector<int>>& matrix, int target) {
int n = matrix.size();
// Start from bottom-left because moving up makes values smaller
// and moving right makes values larger.
int row = n - 1;
int col = 0;
// This stores how many values are less than or equal to target.
int count = 0;
while (row >= 0 && col < n) {
// If this value is small enough, every value above it in this column is also small enough.
if (matrix[row][col] <= target) {
count += row + 1;
col++;
} else {
// If this value is too large, move upward to try a smaller value in the same column.
row--;
}
}
return count;
}
public:
/*
Returns the kth smallest value using binary search
on the possible answer range.
*/
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
// The answer cannot be smaller than the first value.
int low = matrix[0][0];
// The answer cannot be larger than the last value.
int high = matrix[n - 1][n - 1];
while (low < high) {
// This avoids overflow while finding the middle possible answer.
int mid = low + (high - low) / 2;
// Count tells whether mid is large enough to include at least k values.
int count = countLessEqual(matrix, mid);
// If at least k values are <= mid, the answer may be mid or smaller.
if (count >= k) {
high = mid;
} else {
// If fewer than k values are <= mid, the answer must be larger than mid.
low = mid + 1;
}
}
return low;
}
};
// Driver code starts
int main() {
vector<vector<int>> matrix = {
{1, 5, 9},
{10, 11, 13},
{12, 13, 15}
};
int k = 8;
Solution obj;
cout << obj.kthSmallest(matrix, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N x log(maxValue - minValue)), N is the number of rows, because each counting step takes O(N) time using binary search as we are skipping a column or row at each step and binary search runs over the value range.

Space Complexity: O(1), because constant space is used.

Interview follow-up Questions

The matrix rows and columns are sorted, but the whole matrix is not one flat sorted array. For example, the next value after the end of one row is not always larger than all previous row values. So binary search on indexes does not correctly follow sorted order.

SortingMathsTwo PointerBinary SearchArrays

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0] , mat[1][1] , and mat[2][2] . Input: mat = [[10, 20, 30], [40, 50, 60]] Output: 10 50 Exp...

67.1k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the target value is...

98.4k
Comments0