The K Weakest Rows in a Matrix: Binary Search + Sorting

You are given an m x n binary matrix where each row represents a group of soldiers (1s) followed by civilians (0s). A row is "weaker" than another if it has fewer soldiers, or if the soldier counts are equal and the row index is smaller. Given an integer k, return the indices of the k weakest rows, ordered from weakest to strongest.

This is LeetCode 1337: The K Weakest Rows in a Matrix, and it is a great problem for combining binary search with sorting. The matrix structure gives you a shortcut that many people miss: because each row is already sorted, you can count soldiers in logarithmic time instead of scanning every cell.

Why this problem matters

At first glance, this looks like a simple counting and sorting problem. You could scan each row, count the 1s, sort by count, and return the first k indices. That works, but it misses the key insight baked into the problem's structure.

Each row is guaranteed to have all 1s before all 0s. That sorted property means you can use binary search to find the boundary between soldiers and civilians. Instead of O(n) per row to count soldiers, you get O(log n) per row. For large matrices, this difference matters.

The problem also reinforces a pattern you will see again and again: when the input has structure, exploit it. Sorted rows mean binary search. Binary search means logarithmic time. Recognizing when a problem hands you sorted data is a skill that transfers to dozens of other problems.

The approach

The algorithm has three parts:

1. Count soldiers per row. For each row, use binary search to find the index of the first 0. That index equals the number of soldiers.
2. Sort by (soldier_count, row_index). Python's sort is stable and compares tuples lexicographically, so ties in soldier count automatically break by row index.
3. Return the first k indices. Slice the sorted list and extract the row indices.

import bisect

def k_weakest_rows(mat: list[list[int]], k: int) -> list[int]:
    counts = []
    for i, row in enumerate(mat):
        soldiers = bisect.bisect_left(row, 0)
        counts.append((soldiers, i))

    counts.sort()
    return [idx for _, idx in counts[:k]]

Step-by-step walkthrough

Let's trace through the example matrix with k = 3.

Row 2 has only 1 soldier, making it the weakest. Rows 0 and 3 are tied at 2 soldiers each, but row 0 wins the tiebreaker because its index is smaller. The final answer is [2, 0, 3].

Here is the same solution written with a manual binary search instead of bisect, which is useful if you want to practice the binary search template:

def k_weakest_rows(mat: list[list[int]], k: int) -> list[int]:
    def count_soldiers(row):
        lo, hi = 0, len(row)
        while lo < hi:
            mid = (lo + hi) // 2
            if row[mid] == 1:
                lo = mid + 1
            else:
                hi = mid
        return lo

    counts = [(count_soldiers(row), i) for i, row in enumerate(mat)]
    counts.sort()
    return [idx for _, idx in counts[:k]]

Complexity analysis

Time for the binary search approach is O(m * log n + m log m), where m is the number of rows and n is the number of columns. Binary search takes O(log n) per row, and sorting the m pairs takes O(m log m). For most inputs, the sorting step dominates.

Space is O(m) for the list of (count, index) pairs. The output list itself takes O(k) space, which is at most O(m).

Edge cases to watch for

• All rows identical. Every row has the same number of soldiers. The sort falls back to row index order, so you return [0, 1, 2, ..., k-1].
• k equals m. You need to return all row indices. The sort still determines the order.
• A row of all 1s. Binary search returns n (the full row length) as the soldier count. No special handling needed.
• A row of all 0s. Binary search returns 0. This row is the weakest possible.
• Single row matrix. m = 1 and k = 1. Return [0].
• Single column matrix. Each row has exactly one cell. Binary search still works correctly.

The building blocks

1. Binary search on a sorted property

The pattern of using binary search to find a boundary in a sorted sequence:

lo, hi = 0, len(row)
while lo < hi:
    mid = (lo + hi) // 2
    if row[mid] == 1:
        lo = mid + 1
    else:
        hi = mid

This is the "leftmost insertion point" binary search. You are looking for the first index where the value transitions from 1 to 0. The same template applies to any problem where you need to find a threshold or boundary in sorted data. You will reuse it in "First Bad Version," "Find Minimum in Rotated Sorted Array," and "Search Insert Position."

2. Tuple sorting for multi-key ordering

The pattern of sorting tuples to handle tiebreakers:

counts = [(soldiers, row_index) for ...]
counts.sort()

Python sorts tuples lexicographically. The first element is the primary key, the second is the tiebreaker. This eliminates the need for a custom comparator. You will see this pattern in "Merge Intervals," "Task Scheduler," and any problem where you sort by one criterion and break ties with another.

From understanding to recall

You have seen how binary search counts soldiers in O(log n) per row, and how tuple sorting handles the ranking and tiebreaking. The logic is clean, and bisect_left makes the code compact. But under interview pressure, the details matter. Do you search for 0 or for 1? Do you use bisect_left or bisect_right? Is the tuple (count, index) or (index, count)?

These are not conceptual gaps. They are recall gaps, and spaced repetition is how you close them. You practice writing the binary search boundary finder and the tuple-sort pattern from memory at increasing intervals. After a few rounds, the template is automatic. You see "sorted rows" in a problem description, and the binary search setup flows out without hesitation.

Related posts

• Binary Search - The core binary search pattern used to count soldiers efficiently
• Kth Largest Element - Another problem about finding the k-th ranked element
• Search a 2D Matrix - Applying binary search to matrix problems

CodeBricks breaks The K Weakest Rows in a Matrix into its binary search counting and tuple sorting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a binary search problem shows up in your interview, you do not think about it. You just write it.