The K Weakest Rows In A Matrix - Leetcode Solution

The K Weakest Rows in a Matrix problem on LeetCode is a fairly straightforward problem that can be solved through several approaches. In essence, the problem statement is as follows:

Given a two-dimensional matrix called mat, where each row represents a group of soldiers and each column represents the number of soldiers in a regimental unit, return the indices of the k weakest rows in the matrix in ascending order of their strength.

To put it in simpler terms, the goal is to identify the lexicographically smallest k rows in the matrix, based on the sum of their elements.

One brute-force solution to this problem involves iterating through all the rows of the matrix, calculating the corresponding sums, and then sorting the rows based on their sum values. In this case, we can use a dictionary to store the sum and index of each row, sort the dictionary based on the sum values, and finally return the indices of the k weakest rows.

However, a more efficient solution to the problem involves using a min-heap data structure to maintain the k smallest sums while iterating through the rows. This approach involves the following steps:

1. Initialize an empty min heap.
2. Iterate through the rows of the matrix, and for each row, calculate the sum of its elements.
3. Push a tuple into the min heap containing the sum and the index of the current row.
4. If the size of the min heap exceeds k, pop the top element, as it represents the highest sum.
5. Once all the rows have been added to the min heap, pop the remaining elements and append their indices to a result list.
6. Return the result list in ascending order.

Here's the Python code to implement the above solution:

import heapq

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        heap = []
        
        for i in range(len(mat)):
            s = sum(mat[i])
            heapq.heappush(heap, (s, i))
            
            if len(heap) > k:
                heapq.heappop(heap)
        
        result = []
        while heap:
            result.append(heapq.heappop(heap)[1])
            
        return result[::-1]

In this implementation, we use the 'heapq' module in Python as an implementation of the min heap. The 'heappush' and 'heappop' functions allow us to add and remove elements from the heap with O(log k) time complexity. The final result is returned in descending order, hence the use of the '[::-1]' list slicing syntax.

Overall, this solution has a time complexity of O(m log k), where m represents the number of rows in the matrix, which is significantly faster than the O(m log m) time complexity of the brute-force approach.

1