# Solution: The K Weakest Rows in a Matrix

Let’s solve the The K Weakest Rows in a Matrix problem using the Modified Binary Search pattern.

## We'll cover the following

## Statement

You are given an

A row

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

**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

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 (

Next, the algorithm will employ a max-heap to track the `(strength, index)`

, where `strength`

will represent the number of soldiers and `index`

will represent the row number.

The detailed steps of the algorithm are as follows:

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.The binary search works by adjusting the low and high pointers until the number of

$1$ s (soldiers) is determined.We use a priority queue (heap) to keep track of the weakest rows.

`strength`

: The number of soldiers in the row. This allows rows with fewer soldiers to have higher priority in the heap.`i`

: 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.

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 is the one with the smallest strength or the row with the most soldiers).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:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.