The K Weakest Rows in a Matrix

Problem Description

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:

• The number of soldiers in row i is less than the number of soldiers in row j.
• Both rows have the same number of soldiers and i < j.

Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.

Key Insights

• Each row can be evaluated based on the count of 1's (soldiers).
• The matrix is structured such that all soldiers are to the left of civilians.
• Sorting can be performed based on two criteria: the count of soldiers and the row index.
• A straightforward approach involves counting soldiers and then sorting the results.

Space and Time Complexity

Time Complexity: O(m * n + m log m) where m is the number of rows and n is the number of columns; we count soldiers in O(m * n) and sort the results in O(m log m). Space Complexity: O(m) for storing the counts and indices of the rows.

Solution

To solve the problem, we can follow these steps:

1. Count the number of soldiers (1's) in each row. This can be done efficiently since all soldiers are grouped to the left.
2. Create a list of tuples where each tuple contains the count of soldiers and the row index.
3. Sort this list first by the count of soldiers and then by the row index to handle ties.
4. Extract the indices of the first k weakest rows from the sorted list.

We will use a list to store the counts and another data structure for sorting. This approach ensures that we respect the ordering rules given in the problem.

Code Solutions