Kth Smallest in Sorted Matrix (Heap)
Mahabharata — The kth Rank — A Heap-Based Search Through the Grid
क्रमबद्ध जाल में k-वां — ढेर-सूचक विधि से। k बार निकालो न्यूनतम — तत् उत्तरम्॥
*kth in sorted grid — via heap-pointer method. Extract minimum k times — that is the answer.*
The Story
Same problem as bs-21, but solved with a min-heap (Heap-as-Pointer approach).
For `matrix=[[1,5,9],[10,11,13],[12,13,15]]`, k=8: answer=13.
**Min-Heap approach:** - Start from (0,0) — the global minimum - Min-heap stores (value, row, col) - When extracting (r,c): push (r+1,c) and (r,c+1) if valid and not visited - Extract k times → kth extraction is the answer
```java pq.offer(new int[]{matrix[0][0], 0, 0}); bool[][] visited = new bool[n][n]; visited[0][0] = true; for (int i=0; i<k-1; i++) { int[] top = pq.poll(); int r=top[1], c=top[2]; if (r+1<n && !visited[r+1][c]) { pq.offer(new int[]{matrix[r+1][c],r+1,c}); visited[r+1][c]=true; } if (c+1<n && !visited[r][c+1]) { pq.offer(new int[]{matrix[r][c+1],r,c+1}); visited[r][c+1]=true; } } return pq.peek()[0]; ```
**Why push (r+1,c) and (r,c+1)?** In a row+column sorted matrix, the candidates for the next minimum are always to the right or below the current position. The visited array prevents duplicates (e.g., cell (1,1) can be pushed from both (0,1) and (1,0)).
**Alternative without visited array:** Only push (r,c+1) and... hmm, we need visited OR only push (r+1,c) from cells where c==0.
This approach is more natural for linked lists but uses O(k) space for the heap and O(n²) for visited. The binary-search approach (bs-21) uses O(1) space.
Trace `[[1,5],[10,11]]`, k=3: - Init: pq=[(1,0,0)], visited[0][0]=true - Extract 1 (i=0): push (10,1,0),(5,0,1). pq=[(5,0,1),(10,1,0)] - Extract 5 (i=1): push (11,0,2)→invalid (n=2), push (10,1,1)? visited[1][0]=false: already pushed? No: push (11,1,1). pq=[(10,1,0),(11,1,1)] - Return pq.peek()[0]=10 (3rd smallest of [1,5,10,11]) ✓
The Flatten and Sort Approach
Flatten matrix, sort, return k-1 element. O(n² log n).
public int kthSmallestBruteForce(int[][] matrix, int k) {
int n=matrix.length;
int[] flat=new int[n*n];
int idx=0;
for (int[] row:matrix) for (int v:row) flat[idx++]=v;
Arrays.sort(flat);
return flat[k-1];
}The Heap-Pointer Expansion Wisdom
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
boolean[][] visited = new boolean[n][n];
pq.offer(new int[]{matrix[0][0], 0, 0});
visited[0][0] = true;
for (int i = 0; i < k - 1; i++) {
int[] top = pq.poll();
int r = top[1], c = top[2];
if (r + 1 < n && !visited[r+1][c]) {
pq.offer(new int[]{matrix[r+1][c], r+1, c});
visited[r+1][c] = true;
}
if (c + 1 < n && !visited[r][c+1]) {
pq.offer(new int[]{matrix[r][c+1], r, c+1});
visited[r][c+1] = true;
}
}
return pq.peek()[0];
}Step-by-Step Walkthrough
[[1,2],[3,4]], k=2 Init: [(1,0,0)] i=0: poll (1). Push (3,1,0),(2,0,1). pq=[(2,0,1),(3,1,0)] Return peek=2 ✅
Deep Insight
**bs-21 vs hp-9 tradeoffs:** | | bs-21 (binary search) | hp-9 (heap) | |---|---|---| | Time | O(n log(max-min)) | O(k log k) | | Space | O(1) | O(n²) (visited) or O(k) | | Best for | Large value range | Small k |
For very small k (e.g., k=1,2,3), heap approach is faster. For general k, binary search has better space complexity.
**Without visited array (smarter initialization):** Only push the first column into the heap initially (these are the minimums of each row). Then when extracting (r,c): push (r,c+1) only. This uses O(n) heap space without visited array — a cleaner approach that avoids the duplicate issue entirely.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n² log n) | O(n²) | Flatten + sort |
| Optimal | O(k log k) | O(k + n²) | k heap operations + visited array |
Pattern Recognition
✅ Heap-as-pointer for matrix traversal ✅ Start at (0,0); push right and down from each extracted cell ✅ visited array prevents duplicate insertions ✅ k-1 extractions; peek() = kth smallest **LeetCode Trigger Phrases:** → "kth smallest element in sorted matrix" (heap variant) → BFS-like expansion from minimum in 2D grid → Heap pointer traversal of sorted matrix
Bhagavad Gita 2.55
प्रजहाति यदा कामान्सर्वान्पार्थ मनोगतान्। आत्मन्येवात्मना तुष्टः स्थितप्रज्ञस्तदोच्यते॥
When one completely gives up all selfish desires of the mind, O Partha, and is satisfied in the Self alone by the Self — then that person is said to be of steady wisdom.
Connection: The heap extracts with perfect priority — always the minimum, expanding its awareness into adjacent cells. It never skips ahead or backtracks. It achieves exactly k expansions to find the kth smallest — no more, no less. Like the steady sage who desires only what is necessary and remains content with the Self, the algorithm extracts exactly k times with perfect focus, finding the answer without a single wasted operation.