Watch 10 video solutions for The K Weakest Rows in a Matrix, a easy level problem involving Array, Binary Search, Sorting. This walkthrough by Algorithms Made Easy has 10,418 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1's will appear to the left of all the 0's in each row.
A row i is weaker than a row j if one of the following is true:
i is less than the number of soldiers in row j.i < j.Return the indices of the k weakest rows in the matrix 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: The number of soldiers in each row is: - Row 0: 2 - Row 1: 4 - Row 2: 1 - Row 3: 2 - Row 4: 5 The rows ordered from weakest to strongest are [2,0,3,1,4].
Example 2:
Input: mat = [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]], k = 2 Output: [0,2] Explanation: The number of soldiers in each row is: - Row 0: 1 - Row 1: 4 - Row 2: 1 - Row 3: 1 The rows ordered from weakest to strongest are [0,2,3,1].
Constraints:
m == mat.lengthn == mat[i].length2 <= n, m <= 1001 <= k <= mmatrix[i][j] is either 0 or 1.Problem Overview: You are given a matrix where each row represents soldiers (1s) followed by civilians (0s). A row is weaker if it has fewer soldiers, or if the counts are equal but the row index is smaller. Return the indices of the k weakest rows in ascending order of strength.
Approach 1: Simple Counting and Sorting (Time: O(mn + m log m), Space: O(m))
Iterate through each row and count the number of soldiers by scanning the entire row. Store pairs like (soldierCount, rowIndex) in an array. After processing all rows, sort the array first by soldier count and then by row index. Finally, return the first k indices from the sorted result. This approach relies on straightforward iteration over the array and standard sorting. It is simple to implement and works well when matrix dimensions are small.
Approach 2: Binary Search for Counting (Time: O(m log n + m log m), Space: O(m))
Each row is sorted with all soldiers appearing before civilians. Instead of scanning the entire row, use binary search to find the first 0. The index of that position equals the number of soldiers in the row. Repeat this for every row and store (soldierCount, rowIndex). Sort the pairs and return the first k indices. This reduces the counting step from O(n) per row to O(log n), which is useful when rows are large.
Alternative Optimization: Min Heap / Priority Queue (Time: O(m log n + m log k), Space: O(k))
Instead of sorting all rows, maintain a heap that tracks the k weakest rows seen so far. For each row, compute the soldier count (via binary search or scan) and push the pair into a heap (priority queue). If the heap grows larger than k, remove the strongest element. This avoids sorting the entire list and is more efficient when m is large but k is small.
Recommended for interviews: The binary search counting approach is usually the expected solution because it leverages the sorted row property and improves counting efficiency. Implementing the simple counting version first demonstrates clarity, while adding binary search or a heap shows deeper algorithmic optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting + Sorting | O(mn + m log m) | O(m) | Best for simple implementation when matrix size is small |
| Binary Search + Sorting | O(m log n + m log m) | O(m) | When rows are sorted and you want faster soldier counting |
| Binary Search + Heap | O(m log n + m log k) | O(k) | Useful when number of rows is large but only k weakest are needed |