Description
Given an n x n
matrix
where each of the rows and columns is sorted in ascending order, return the kth
smallest element in the matrix.
Note that it is the kth
smallest element in the sorted order, not the kth
distinct element.
You must find a solution with a memory complexity better than O(n2)
.
Examples:
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
Solution in Python
Approach:
- Binary Search on Values:
- Since each row and column of the matrix is sorted, the smallest element is at the top-left (
matrix[0][0]
) and the largest element is at the bottom-right (matrix[n-1][n-1]
). - This property allows us to apply binary search on the value range between
matrix[0][0]
andmatrix[n-1][n-1]
to find thek
th smallest element without having to sort all elements.
- Since each row and column of the matrix is sorted, the smallest element is at the top-left (
- Counting Elements:
- For each midpoint during the binary search, we need to count how many elements in the matrix are less than or equal to that midpoint. This count helps us decide whether to search in the left or right half.
- A helper function,
count_less_equal(mid)
, can efficiently count elements less than or equal to a given value by using the sorted property of each row and column:- Start counting from the bottom-left element, moving upwards or to the right depending on whether the current element is less than or equal to
mid
.
- Start counting from the bottom-left element, moving upwards or to the right depending on whether the current element is less than or equal to
- Binary Search Process:
- Initialize
left
tomatrix[0][0]
andright
tomatrix[n-1][n-1]
. - While
left < right
:- Calculate
mid
as the midpoint ofleft
andright
. - Use
count_less_equal(mid)
to count how many elements are less than or equal tomid
. - If the count is less than
k
, adjustleft = mid + 1
to move the search to the right half (looking for larger values). - Otherwise, adjust
right = mid
to move the search to the left half.
- Calculate
- Initialize
- Final Result:
- Once
left == right
, we have narrowed down thek
th smallest element.
- Once
Python
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
# Helper function to count elements <= mid in the matrix
def count_less_equal(mid):
count = 0
row, col = len(matrix) - 1, 0 # Start from the bottom-left corner
while row >= 0 and col < len(matrix):
if matrix[row][col] <= mid:
# All elements in the current row up to col are <= mid
count += row + 1
col += 1
else:
# Move up to find smaller elements
row -= 1
return count
# Binary search on the values in the matrix
left, right = matrix[0][0], matrix[-1][-1]
while left < right:
mid = (left + right) // 2
if count_less_equal(mid) < k:
# Fewer than k elements are <= mid, move right
left = mid + 1
else:
# At least k elements are <= mid, move left
right = mid
# When left == right, we've found the kth smallest element
return left
Explanation of the Code:
count_less_equal(mid)
:- This helper function counts how many elements in the matrix are less than or equal to
mid
by starting from the bottom-left of the matrix. - For each element at
matrix[row][col]
:- If it’s less than or equal to
mid
, all elements above it in the current column are also less than or equal tomid
. So we addrow + 1
to the count and move to the right. - If it’s greater than
mid
, we move one row up to check smaller values in the current column.
- If it’s less than or equal to
- This helper function counts how many elements in the matrix are less than or equal to
- Binary Search:
left
is initialized to the smallest value,matrix[0][0]
, andright
to the largest,matrix[-1][-1]
.- At each step,
mid
is the midpoint ofleft
andright
, and we count elements<= mid
. - Depending on the count, we adjust
left
orright
to continue narrowing down the search range untilleft == right
.
- Result:
- When
left == right
, the search concludes, andleft
(orright
) holds thek
th smallest element.
- When
Solution in C++
C++
class Solution {
public:
// Helper function to count elements in the matrix that are less than or equal to a given value
int countLessEqual(const vector<vector<int>>& matrix, int mid, int n) {
int count = 0;
int row = n - 1; // Start from the bottom-left corner of the matrix
int col = 0;
// Traverse upwards and rightwards to count elements <= mid
while (row >= 0 && col < n) {
if (matrix[row][col] <= mid) {
// All elements in this row up to the current position are <= mid
count += (row + 1);
col++; // Move to the next column
} else {
// Move up to find smaller elements
row--;
}
}
return count;
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size(); // Dimension of the matrix (n x n)
int left = matrix[0][0]; // Smallest element in the matrix
int right = matrix[n - 1][n - 1]; // Largest element in the matrix
// Binary search for the kth smallest element
while (left < right) {
int mid = left + (right - left) / 2;
// Count how many numbers are less than or equal to mid
int count = countLessEqual(matrix, mid, n);
if (count < k) {
// If count is less than k, we need to search in the larger half
left = mid + 1;
} else {
// If count is greater than or equal to k, search in the smaller half
right = mid;
}
}
// 'left' is now the kth smallest element
return left;
}
};
Solution in Javascript
JavaScript
var kthSmallest = function(matrix, k) {
// Define the search range for the binary search
let left = matrix[0][0]; // smallest element in the matrix
let right = matrix[matrix.length - 1][matrix[0].length - 1]; // largest element in the matrix
// Binary search for the kth smallest element
while (left < right) {
// Find the middle element of the current range
const mid = Math.floor((left + right) / 2);
// Count how many elements in the matrix are less than or equal to `mid`
let count = countLessEqual(matrix, mid);
if (count < k) {
// If there are fewer than k elements less than or equal to mid,
// we need to search in the higher range
left = mid + 1;
} else {
// Otherwise, we search in the lower range
right = mid;
}
}
// After the loop, `left` will point to the kth smallest element
return left;
};
function countLessEqual(matrix, x) {
let count = 0;
let n = matrix.length;
let row = n - 1; // start from the last row
let col = 0; // start from the first column
// Traverse the matrix in a zig-zag manner (bottom-left to top-right)
while (row >= 0 && col < n) {
if (matrix[row][col] <= x) {
// If the element is <= x, all elements in this row up to this column
// are also <= x (since each row is sorted), so add `row + 1` to the count
count += row + 1;
col++;
} else {
// Otherwise, move up to the next row
row--;
}
}
return count;
}
Solution in Java
Java
class Solution {
public int kthSmallest(int[][] matrix, int k) {
// Define the initial range of possible values in the matrix
int n = matrix.length;
int left = matrix[0][0]; // Smallest element in the matrix
int right = matrix[n - 1][n - 1]; // Largest element in the matrix
// Perform binary search on the value range
while (left < right) {
int mid = left + (right - left) / 2; // Find the midpoint of the current range
// Count how many elements in the matrix are less than or equal to mid
int count = countLessEqual(matrix, mid, n);
// If count is less than k, search in the upper half of the range
if (count < k) {
left = mid + 1;
} else {
// Otherwise, search in the lower half of the range
right = mid;
}
}
// After the loop, left and right converge to the kth smallest element
return left;
}
// Helper function to count elements <= target in the matrix
private int countLessEqual(int[][] matrix, int target, int n) {
int count = 0;
int row = n - 1; // Start from the last row
int col = 0; // Start from the first column
// Traverse the matrix in a "staircase" manner
while (row >= 0 && col < n) {
if (matrix[row][col] <= target) {
// If the element is <= target, all elements above in this column are also <= target
count += (row + 1);
col++; // Move to the next column
} else {
row--; // Move up in the same column to find smaller elements
}
}
return count;
}
}