The K Weakest Rows in a Matrix

This problem can be solved by using the principles of sorting and selection. We need to count the number of soldiers in each row and then sort the rows based on these counts. The rows are identified by their indices, so we’ll sort them by soldier count first, and by index in case of a tie.

Python solution:

1
2
3
4
5

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        soldier_counts = [(sum(row), i) for i, row in enumerate(mat)]
        soldier_counts.sort()  # sorts first by soldier count, then by index
        return [i for count, i in soldier_counts[:k]]

In the code above, we first count the soldiers in each row using a list comprehension. We store each count along with its corresponding row index in the soldier_counts list.

Then we sort soldier_counts. Since each element is a tuple, the sort operation uses tuple comparison, which compares the first elements of the tuples first (the soldier counts), and only considers the second elements (the indices) in case of a tie.

Finally, we use a list comprehension to return the indices of the k weakest rows.

Claude Explanation

Here are the key steps to solve this problem of finding the k weakest rows in a binary matrix:

  1. Iterate through each row and count the number of 1’s (soldiers) in that row.

  2. Build a list of tuples where each tuple contains the (row index, count of soldiers in that row).

  3. Sort the list of tuples based on:

    • Ascending order of number of soldiers.
    • For rows with same soldier count, sort by ascending row index.

  4. Take the first k tuples from the sorted list.

  5. Return the list of row indices from those k tuples.

This allows us to calculate the strength of each row based on soldier count. We can then sort the rows in order from weakest to strongest using the soldier count and row index as sorting criteria. Finally, we take the first k rows as the indices of the weakest rows.

The key steps are calculating soldiers per row, sorting rows by strength criteria, and taking the first k rows from the sorted list.

Here is an implementation in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def kWeakestRows(self, mat, k):
        # Count soldiers in each row
        rows = []
        for i, row in enumerate(mat):
            count = sum(row)
            rows.append((count, i))

        # Sort by soldier count and index
        rows.sort()

        # Take first k rows  
        weakest_idxs = [idx for count, idx in rows[:k]]

        return weakest_idxs

The key steps are:

  • Iterate each row and count soldiers
  • Append (count, index) tuples to list
  • Sort list based on count and index
  • Take first k indices from sorted list

This follows the logic of counting soldier strength per row, sorting rows by strength, and taking the k weakest row indices.