Kth Weakest Row in Matrix
Mahabharata — The Vulnerable Flanks — Finding the k Least Defended Rows
k-वीं सबसे कमजोर पंक्ति — सैनिक संख्या से। समान सैनिक? पंक्ति क्रमांक निर्णय करे॥
*kth weakest row — measured by soldier count. Tied soldier count? Row index decides.*
The Story
A binary matrix where 1s are soldiers and 0s are civilians. Soldiers are always first (sorted rows). Find the kth weakest row (fewest soldiers; tie broken by smaller row index).
For `mat=[[1,1,0,0,0],[1,1,1,1,0],[1,0,0,0,0],[1,1,0,0,0],[1,1,1,1,1]]`, k=3: answer=2.
**Step 1: Count soldiers per row** using binary search (rows are sorted → first 0 = number of soldiers). **Step 2: Find kth weakest** using a MAX-heap of size k.
Max-heap ordered by (soldiers desc, rowIndex desc) — so the 'weakest' candidate for eviction (most soldiers, or tied soldiers with higher index) sits at top.
```java PriorityQueue<int[]> pq = new PriorityQueue<>( (a,b) -> a[0]!=b[0] ? b[0]-a[0] : b[1]-a[1]); // Max by soldiers, then max by index for (int i=0; i<mat.length; i++) { int soldiers = countSoldiers(mat[i]); // Binary search pq.offer(new int[]{soldiers, i}); if (pq.size() > k) pq.poll(); } return pq.peek()[1]; // Row index of kth weakest ```
**Counting soldiers with binary search:** Rows are sorted (1s before 0s). Binary search for first 0 position = number of soldiers.
```java int countSoldiers(int[] row) { int lo=0, hi=row.length; while (lo<hi) { int mid=(lo+hi)/2; if (row[mid]==1) lo=mid+1; else hi=mid; } return lo; } ```
The Linear Count and Sort
Count soldiers in each row (linear scan). Sort rows by (soldiers, index). Return k-1 row index. O(mn + m log m).
public int kWeakestRowsBruteForce(int[][] mat, int k) {
int m=mat.length;
int[][] pairs=new int[m][2];
for (int i=0;i<m;i++) {
int s=0; for (int v:mat[i]) s+=v;
pairs[i]=new int[]{s,i};
}
Arrays.sort(pairs,(a,b)->a[0]!=b[0]?a[0]-b[0]:a[1]-b[1]);
return pairs[k-1][1];
}The Soldier-Count Binary Search + Max-Heap Wisdom
public int kWeakestRows(int[][] mat, int k) {
PriorityQueue<int[]> pq = new PriorityQueue<>(
(a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]); // Max: more soldiers or higher index at top
for (int i = 0; i < mat.length; i++) {
int lo = 0, hi = mat[i].length;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mat[i][mid] == 1) lo = mid + 1; else hi = mid;
}
pq.offer(new int[]{lo, i}); // lo = soldier count
if (pq.size() > k) pq.poll();
}
return pq.peek()[1];
}Step-by-Step Walkthrough
[[1,0],[0,0],[1,1]], k=1 Row 0: 1 soldier. Row 1: 0 soldiers. Row 2: 2 soldiers. Add (1,0),(0,1)→size=2>1→poll (1,0)→[(0,1)] Add (2,2)→size=2>1→poll (2,2)→[(0,1)] Return peek()[1]=1 (weakest row is row 1 with 0 soldiers) ✅
Deep Insight
**Binary search for soldier count:** Rows are sorted (1s before 0s). Binary search for the first 0 → that's the soldier count. O(log n) per row vs O(n) linear scan.
**Why return pq.peek():** After processing all rows with size-k max-heap, the heap contains the k weakest rows. peek() gives the 'least weak' of the k weakest = the kth weakest overall.
**Return pq.peek()[1]:** The row INDEX. We stored (soldiers, rowIndex) in the heap.
**Combined with hp-5:** Same max-heap pattern for k-minimum selection. The choice of what to maximize in the heap determines what gets evicted.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(mn + m log m) | O(m) | Count all + sort |
| Optimal | O(m log k + m log n) | O(k) | Binary search per row + heap of size k |
Pattern Recognition
✅ kth weakest row = kth smallest by (soldiers, index) ✅ Max-heap with custom comparator (max soldiers at top) ✅ Binary search for soldier count in sorted rows ✅ peek()[1] = row index of kth weakest **LeetCode Trigger Phrases:** → "kth weakest row" in binary matrix → Custom comparison with tiebreaker → Max-heap for k-minimum selection
Bhagavad Gita 16.1
अभयं सत्त्वसंशुद्धिर्ज्ञानयोगव्यवस्थितिः। दानं दमश्च यज्ञश्च स्वाध्यायस्तप आर्जवम्॥
Fearlessness, purity of mind, steadfastness in knowledge and yoga, charity, self-control, and sacrifice, study of scriptures, austerity, integrity...
Connection: The weakest rows have the fewest soldiers — those with the least defensive capacity. The algorithm identifies them not to demean but to understand vulnerability. Like the Gita's enumeration of virtues that need strengthening, recognizing the k weakest points enables targeted reinforcement. The max-heap's ruthless elimination of the strongest rows preserves only those who most need understanding — the k most vulnerable.