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.
In this approach, we directly count the number of soldiers in each row by iterating through the elements of the row, and then sort the rows based on the count followed by their index to determine the order.
Steps to implement:
The C solution involves using a two-dimensional array to track the number of soldiers and their respective row indices. We then use the quicksort function with a custom comparator to sort this array by soldiers' count first and indices as a tiebreaker. Finally, extract the indices of the weakest rows.
Time Complexity: O(m*n + m*log m) due to counting and sorting the rows.
Space Complexity: O(m) to store the row strength information.
This approach uses binary search to efficiently count the number of soldiers in each row. Given that soldiers are always positioned before civilians, binary search can help quickly find the first civilian and thus the count of soldiers.
Implementation steps:
This solution optimizes soldier count using binary search in each row. This reduces the time complexity to efficiently find each row's strength before sorting and extracting indices.
Time Complexity: O(m*log n + m*log m) due to binary search for counting and sorting rows.
Space Complexity: O(m), for maintaining strength array storage.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Simple Counting and Sorting | Time Complexity: O(m*n + m*log m) due to counting and sorting the rows. Space Complexity: O(m) to store the row strength information. |
| Approach 2: Binary Search for Counting | Time Complexity: O(m*log n + m*log m) due to binary search for counting and sorting rows. Space Complexity: O(m), for maintaining strength array storage. |
| Default Approach | — |
| 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 |
The K Weakest Rows in a Matrix | Live Coding with Explanation | Leetcode - 1337 • Algorithms Made Easy • 10,418 views views
Watch 9 more video solutions →Practice The K Weakest Rows in a Matrix with our built-in code editor and test cases.
Practice on FleetCode