617. The K Weakest Rows in a Matrix
You receive an m × n binary matrix mat. Each row represents one row of troops: 1 is a soldier, 0 is a civilian, and within every row all soldiers stand to the left of all civilians (each row is 1s followed by 0s).
Row i is weaker than row j if it contains fewer soldiers, or if both contain the same number and i < j. This makes the ordering total — no two rows ever tie.
Given mat and an integer k, return the indices of the k weakest rows, ordered from weakest to strongest.
Example 1:
Input: 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
Output: [2, 0, 3]
Explanation: Soldier counts per row are [2, 4, 1, 2, 5]. Row 2 is weakest with 1 soldier; rows 0 and 3 both have 2, and the smaller index 0 ranks weaker; so the three weakest are 2, 0, 3.
Example 2:
Input: mat = [[1,0,0,0],[0,0,0,0],[1,0,0,0],[1,0,0,0]], k = 2
Output: [1, 0]
Explanation: Counts are [1, 0, 1, 1]. Row 1 has no soldiers at all; among rows 0, 2, 3 (one soldier each) the smallest index, 0, comes next.
Constraints:
- 1 ≤ m, n ≤ 100
- 1 ≤ k ≤ m
- mat[i][j] is 0 or 1
- In every row, all 1s appear before all 0s.
Hints:
Each row's strength is just its number of soldiers. Compute all m counts, pair each with its row index, and pick the k smallest pairs — ties break themselves because the index is part of the pair.
The rows are sorted (1s then 0s), so you don't need to sum n cells: binary search for the first 0 — its position IS the soldier count, in O(log n) per row.
To avoid sorting all m rows for just k winners, keep a max-heap of size k: push each (count, index), and evict the strongest whenever the heap grows past k.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: 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
Expected output: [2, 0, 3]