Leetcode 378: Kth Smallest Element in a Sorted Matrix
grid47 Exploring patterns and algorithms
Sep 30, 2024
6 min read
Solution to LeetCode 378: Kth Smallest Element in a Sorted Matrix Problem
Given an n x n matrix where each row and column is sorted in ascending order, find the kth smallest element in the matrix. The matrix is sorted in both rows and columns, but the kth smallest element is the one in the sorted order, not necessarily distinct.
Problem
Approach
Steps
Complexity
Input: The input consists of a matrix with n rows and n columns, where each element in the matrix is sorted in non-decreasing order. You are also given a value k.
• Explanation: The sorted matrix elements are [1, 5, 9, 10, 11, 12, 13, 13, 15]. The 8th smallest element is 13.
• Input: matrix = [[-5]], k = 1
• Explanation: The only element in the matrix is -5, so the 1st smallest element is -5.
Approach: We can solve this problem by using a priority queue (min-heap) to efficiently track the smallest elements in the matrix.
Observations:
• Since the matrix is sorted, we can use a priority queue to extract the smallest elements efficiently.
• The priority queue will allow us to track the smallest element and ensure that we find the kth smallest element without having to sort the entire matrix.
Steps:
• Create a priority queue and insert the first element of each row into the queue.
• Pop the smallest element and push the next element from the same row into the queue.
• Repeat this process k times to extract the kth smallest element.
Empty Inputs:
• The input matrix will always be non-empty as per the problem constraints.
Large Inputs:
• The algorithm should handle up to the maximum constraints efficiently, with matrix size up to 300 x 300.
Special Values:
• The matrix may contain negative values, and the kth smallest element can be negative as well.
Constraints:
• The value of k will always be valid, and the matrix is guaranteed to be sorted.
intkthSmallest(vector<vector<int>>& mtx, int k) {
int m = mtx.size(), n = mtx[0].size();
priority_queue<vector<int>, vector<vector<int>>, greater<>> pq;
for(int r =0; r < min(m, k); r++)
pq.push({mtx[r][0], r, 0});
vector<int> cur;
while(k-->1&&!pq.empty()) {
cur = pq.top();
pq.pop();
if(cur[2] +1< n)
pq.push({ mtx[cur[1]][cur[2] +1], cur[1], cur[2] +1 });
}
cur = pq.top();
return cur[0];
}
1 : Function Declaration
intkthSmallest(vector<vector<int>>& mtx, int k) {
Declares the function `kthSmallest` which takes a matrix `mtx` and an integer `k` as inputs, and returns the kth smallest element from the matrix.
2 : Matrix Dimensions
int m = mtx.size(), n = mtx[0].size();
Extracts the number of rows (`m`) and columns (`n`) from the matrix `mtx`.
Initializes a min-heap priority queue `pq` to store elements in ascending order. Each element in the queue is a vector containing a matrix element, its row index, and its column index.
4 : Loop Initialization
for(int r =0; r < min(m, k); r++)
Loops through the first `k` rows (or less if the matrix has fewer rows) and pushes the first element of each row into the priority queue.
5 : Heap Insertion
pq.push({mtx[r][0], r, 0});
Pushes a triplet (value, row index, column index) for the first element of each row into the priority queue.
6 : Vector Declaration
vector<int> cur;
Declares a vector `cur` to temporarily store the current smallest element and its indices from the priority queue.
7 : Main Loop
while(k-->1&&!pq.empty()) {
Runs a loop to extract the smallest element from the heap `k-1` times, ensuring that the heap contains the next smallest elements.
8 : Heap Top Extraction
cur = pq.top();
Extracts the top (smallest) element from the priority queue into the `cur` vector.
9 : Heap Pop
pq.pop();
Removes the extracted top element from the priority queue.
10 : Next Element Insertion
if(cur[2] +1< n)
Checks if the next element in the current row exists (i.e., the current column index is within bounds).
