Weakest Squads
Problem
A training camp records its squads in a binary matrix grid: row i describes squad i, where 1 is a veteran and 0 a recruit. In every row all the 1s come before all the 0s. A squad is weaker than another if it has fewer veterans; with equal veterans, the squad with the smaller row index is the weaker one.
Return the indices of the k weakest squads, weakest first.
Example 1
- Input:
- grid = [[1,1,0,0], [1,1,1,1], [1,0,0,0], [1,1,0,0], [1,1,1,0]], k = 3
- Output:
- [2, 0, 3]
Veterans per squad: 2, 4, 1, 2, 3. Weakest is squad 2 (1), then squads 0 and 3 (2 each, index order).
Example 2
- Input:
- grid = [[1,1], [0,0], [1,0]], k = 2
- Output:
- [1, 2]
Constraints
- 1 ≤ rows, cols ≤ 300
- grid[i][j] is 0 or 1, with all 1s before all 0s in each row
- 1 ≤ k ≤ rows
Hint
Show the first hint
Each row is sorted (1s, then 0s). How fast can you count its 1s?
Walkthrough
How to approach it
01Clarify before coding
- Are rows guaranteed to be 1s followed by 0s? Yes, which allows binary search.
- How are ties broken? Smaller row index is weaker.
- Output order? Weakest first.
02Brute force
Count the 1s in every row by scanning it, then sort all rows by (count, index) and take k.
Cost: O(m·n + m log m). For 300 × 300 that is fine, but it ignores both the sorted rows and the fact that only k rows matter.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.