Dare2Solve
Given an m x n
matrix where each of the rows and columns is sorted in ascending order, find the k-th smallest element in the matrix.
Since the matrix is sorted in ascending order both row-wise and column-wise, the k-th smallest element can be efficiently found using a max-heap. The idea is to keep track of the k smallest elements seen so far. By using a max-heap, we can easily ensure that only the k smallest elements are retained.
k
, remove the largest element from the heap to maintain only the k smallest elements.class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
priority_queue<int> maxHeap; // Max-Heap for storing k smallest elements
for (const auto& row : matrix) {
for (int num : row) {
maxHeap.push(num);
if (maxHeap.size() > k) {
maxHeap.pop();
}
}
}
return maxHeap.top();
}
};
class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
max_heap = []
for row in matrix:
for num in row:
heapq.heappush(max_heap, -num) # Use negative values to simulate a max-heap
if len(max_heap) > k:
heapq.heappop(max_heap)
return -max_heap[0]
class Solution {
public int kthSmallest(int[][] matrix, int k) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // Max-Heap for k smallest elements
for (int[] row : matrix) {
for (int num : row) {
maxHeap.offer(num);
if (maxHeap.size() > k) {
maxHeap.poll();
}
}
}
return maxHeap.peek();
}
}
var kthSmallest = function (matrix, k) {
const heap = new MaxPriorityQueue()
for (let i = 0; i < matrix.length; i++) {
for (num of matrix[i]) {
heap.enqueue(num)
if (heap.size() > k) {
heap.dequeue()
}
}
}
return heap.front().element
};