The K Weakest Rows in a Matrix

Difficulty: Easy | Acceptance: 74.40% | Paid: No Topics: Array, Binary Search, Sorting, Heap (Priority Queue), Matrix

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.

• Examples
• Constraints
• Brute Force with Sorting
• Binary Search + Sorting
• Min-Heap (Priority Queue)
• Bucket Sort

Examples

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
The rows ordered from weakest to strongest are [2,0,3,1,4].

Input: mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
Output: [0,2]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 1 
- Row 1: 4 
- Row 2: 1 
- Row 3: 1 
The rows ordered from weakest to strongest are [0,2,3,1].

Constraints

m == mat.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
mat[i][j] is either 0 or 1.

Brute Force with Sorting

Intuition Count the number of 1s in each row by scanning, then sort rows by (count, index) and return the first k indices.

Steps

• Iterate through each row and count the number of 1s
• Store pairs of (count, row_index) in an array
• Sort the array by count first, then by index
• Return the first k row indices

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        rows = [(sum(row), i) for i, row in enumerate(mat)]
        rows.sort()
        return [i for _, i in rows[:k]]

Complexity

• Time: O(m × n + m × log(m))
• Space: O(m)
• Notes: Simple but not optimal for counting 1s in sorted rows

Binary Search + Sorting

Intuition Since each row is sorted, use binary search to find the first 0 (count of 1s) efficiently, then sort and return k weakest.

Steps

• For each row, use binary search to find the index of first 0
• The count of 1s equals that index
• Store (count, row_index) pairs and sort
• Return first k indices

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        def countSoldiers(row):
            left, right = 0, len(row)
            while left < right:
                mid = (left + right) // 2
                if row[mid] == 1:
                    left = mid + 1
                else:
                    right = mid
            return left
        
        rows = [(countSoldiers(row), i) for i, row in enumerate(mat)]
        rows.sort()
        return [i for _, i in rows[:k]]

Complexity

• Time: O(m × log(n) + m × log(m))
• Space: O(m)
• Notes: Better than brute force for counting, leverages sorted row property

Min-Heap (Priority Queue)

Intuition Use a min-heap to maintain rows ordered by (soldier_count, row_index), then extract k elements to get the weakest rows.

Steps

• Count soldiers in each row using binary search
• Push (count, index) pairs into a min-heap
• Extract k elements from the heap
• Return the indices in order

import heapq

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        def countSoldiers(row):
            left, right = 0, len(row)
            while left < right:
                mid = (left + right) // 2
                if row[mid] == 1:
                    left = mid + 1
                else:
                    right = mid
            return left
        
        heap = []
        for i, row in enumerate(mat):
            count = countSoldiers(row)
            heapq.heappush(heap, (count, i))
        
        result = []
        for _ in range(k):
            result.append(heapq.heappop(heap)[1])
        return result

Complexity

• Time: O(m × log(n) + m × log(m) + k × log(m))
• Space: O(m)
• Notes: Useful when k is much smaller than m, can optimize with max-heap of size k

Bucket Sort

Intuition Since the maximum number of soldiers per row is at most n (number of columns), use bucket sort where each bucket stores row indices with that specific soldier count.

Steps

• Create n+1 buckets (for counts 0 to n)
• For each row, count soldiers using binary search and add index to corresponding bucket
• Iterate through buckets in order, collecting indices until we have k results

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        def countSoldiers(row):
            left, right = 0, len(row)
            while left < right:
                mid = (left + right) // 2
                if row[mid] == 1:
                    left = mid + 1
                else:
                    right = mid
            return left
        
        n = len(mat[0])
        buckets = [[] for _ in range(n + 1)]
        
        for i, row in enumerate(mat):
            count = countSoldiers(row)
            buckets[count].append(i)
        
        result = []
        for bucket in buckets:
            for idx in bucket:
                result.append(idx)
                if len(result) == k:
                    return result
        return result

Complexity

• Time: O(m × log(n) + n + k)
• Space: O(m + n)
• Notes: Optimal when n is small, avoids sorting overhead