Sponsored
Sponsored
By using a min-heap (priority queue), you can efficiently extract the smallest elements one by one. Initially, insert the first element of each row into the heap. Then, repeat the process of extracting the smallest element and inserting the next element from the corresponding row. Continue this until you extract the k-th smallest element.
Time Complexity: O(k log n), where n is the size of each row/column.
Space Complexity: O(n), due to the maintained heap.
1import java.util.PriorityQueue;
2
3class Solution {
4 public int kthSmallest(int[][] matrix, int k) {
5 int n = matrix.length;
6 PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(matrix[a[0]][a[1]], matrix[b[0]][b[1]]));
7
8 for (int i = 0; i < Math.min(n, k); i++)
9 minHeap.offer(new int[]{i, 0});
10
11 int val = 0;
12 while (k-- > 0) {
13 int[] pos = minHeap.poll();
14 int r = pos[0], c = pos[1];
15 val = matrix[r][c];
16 if (c < n - 1)
17 minHeap.offer(new int[]{r, c + 1});
18 }
19
20 return val;
21 }
22}In this Java solution, we implement the min-heap using a PriorityQueue. At the beginning, the smallest elements from each row are added to the heap. By always processing (extracting) the smallest from the heap first, we ensure that we move across our matrix consistently by their natural sorted order. Finally, the k-th extracted element will be the required result.
This approach uses binary search over the range of possible values in the matrix to find the k-th smallest element. The idea is to repeatedly narrow the range by counting the number of elements in the matrix that are less than or equal to the current middle value. Depending on this count, adjust the binary search range to hone in on the k-th smallest element.
Time Complexity: O(n log(max-min)), resulting from binary search log sweeps invoking count linear phase.
Space Complexity: O(1), since alterations occur in-place within computation limits of primitive variables.
This C solution employs binary search on the matrix's values. By calculating the number of elements less than or equal to the mid-point value in the range, the solution dynamically adjusts search bounds until the k-th smallest is uncovered at the low-end track of the narrowed range. The logic banks on ordered nature without direct sorting.