Solution: The K Weakest Rows in a Matrix

Statement

You are given an $m \times n$ binary matrix of $1$’s (representing soldiers) and $0$’s (representing civilians). The soldiers are positioned in front of the civilians, i.e., 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 any 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 \lt j$.

You have to return the indexes of the $k$ weakest rows in the matrix ordered from weakest to strongest.

Constraints:

• $m =$ matrix.length

• $n =$ matrix[i].length

• $2 \leq n, m \leq 100$

• $1 \leq k \leq m$

• matrix[i][j] is either $0$ or $1$.

Solution

The problem involves finding the weakest rows in a binary matrix, where soldiers (represented by $1$s) appear before civilians (represented by $0$s) in each row. A combination of binary search and a priority queue (heap) is used to solve this efficiently.

The algorithm first calculates the number of soldiers in each row using a binary search. Since the matrix guarantees that soldiers will always appear before civilians, a binary search can quickly determine the number of soldiers by identifying the first occurrence of a civilian ($0$) in each row.

Next, the algorithm will employ a max-heap to track the $k$ weakest rows. The rows will be inserted into the heap as pairs of (-strength, -index), where strength will represent the number of soldiers and index will represent the row number. Using negative values will ensure that weaker rows are prioritized, and in case of a tie in soldier count, the row with the smaller index will be considered weaker.

The detailed steps of the algorithm are as follows:

1. The first step is to perform a binary search on each row to count the number of soldiers ($1$s) present. Since the matrix rows are sorted with all $1$s appearing before the $0$s, binary search helps count soldiers in logarithmic time.

2. The binary search works by adjusting the low and high pointers until the number of $1$s (soldiers) is determined.

3. We use a priority queue (heap) to keep track of the weakest rows. As Python’s heapq library provides a min-heap, we simulate a max-heap by storing negative values. Specifically, we store:

   1. -strength: Negative of the number of soldiers in the row. This allows rows with fewer soldiers to have higher priority in the heap.

   2. -i: Negative of the row index to break ties by row number, ensuring that the row with the smaller index is considered weaker if two rows have the same number of soldiers.

4. As we iterate through the rows, we push each row’s strength and index into the heap. If the heap grows larger than k, we remove the strongest row (which, due to the negative values, is the one with the smallest negative strength or the row with the most soldiers).

5. Finally, after processing all rows, we extract the indexes of the weakest rows from the heap. Since the weakest rows come out in reverse order (strongest to weakest), we reverse the result before returning.

The heap ensures that only the k weakest rows are kept, and we efficiently manage the sorting and selection using this approach.

Now, let’s look at the following illustration to get a better understanding of the solution: