Domain 1EasyCORE

The K Weakest Rows in a Matrix

The problem requires us to identify the `k` weakest rows in a binary matrix where soldiers (represented by `1`s) are positioned before civilians (represented by `0`s). The strength of a row is determined by the number of soldiers it contains. If two rows have the same number of soldiers, the row with the smaller index is considered weaker.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Binary Search

1337. The K Weakest Rows in a Matrix

Model: qwen2.5-coder:14b
Topics: Array,Binary Search
FAANG asked: 1
Acceptance rate: 72.0%


Problem Breakdown

The problem requires us to identify the k weakest rows in a binary matrix where soldiers (represented by 1s) are positioned before civilians (represented by 0s). The strength of a row is determined by the number of soldiers it contains. If two rows have the same number of soldiers, the row with the smaller index is considered weaker.

Inputs:

  • A 2D binary matrix mat where each row is sorted such that all 1s come before any 0s.
  • An integer k representing the number of weakest rows to return.

Outputs:

  • A list of indices of the k weakest rows in ascending order of their strength.

Implicit Constraints/Edge Cases:

  • The matrix can be empty or have only one row/column.
  • All elements are either 0 or 1.
  • The number of soldiers in each row is non-decreasing from left to right.

Intuition

A brute-force approach would involve counting the number of soldiers in each row and then sorting these counts along with their indices. However, this approach has a time complexity of (O(m \times n + m \log m)), which can be inefficient for larger matrices.

The key insight is to leverage the sorted nature of each row to efficiently count the number of soldiers using binary search. This reduces the counting step to (O(\log n)) per row, improving the overall time complexity to (O(m \log n + m \log m)).

Approach

  1. Binary Search for Counting Soldiers:

    • For each row in the matrix, use binary search to find the first occurrence of 0. The index of this 0 gives the count of soldiers in that row.
  2. Pairing Indices with Soldier Counts:

    • Create a list of tuples where each tuple contains the row index and its corresponding soldier count.
  3. Sorting by Strength:

    • Sort the list of tuples primarily by the number of soldiers (ascending) and secondarily by the row index (ascending).
  4. Extracting Indices:

    • Extract the indices from the sorted list to get the k weakest rows.

Complexity Analysis

  • Time Complexity: (O(m \log n + m \log m))

    • Binary search for each row takes (O(\log n)).
    • Sorting the list of tuples takes (O(m \log m)).
  • Space Complexity: (O(m))

    • We store a list of tuples containing indices and soldier counts.

Solution

def kWeakestRows(mat, k):
    # Step 1: Count soldiers in each row using binary search
    def count_soldiers(row):
        left, right = 0, len(row) - 1
        while left <= right:
            mid = (left + right) // 2
            if row[mid] == 1:
                left = mid + 1
            else:
                right = mid - 1
        return left
    
    # Step 2: Pair each row index with its soldier count
    indexed_strengths = [(i, count_soldiers(row)) for i, row in enumerate(mat)]
    
    # Step 3: Sort by number of soldiers (and by index if tied)
    indexed_strengths.sort(key=lambda x: (x[1], x[0]))
    
    # Step 4: Extract the first k indices
    return [index for index, _ in indexed_strengths[:k]]

# Example usage:
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
print(kWeakestRows(mat, k))  # Output: [2, 0, 3]

Edge Cases Handled

  • Empty Matrix: The function will return an empty list since there are no rows to evaluate.
  • Single Row/Column: The binary search and sorting steps handle these cases gracefully without additional checks.
  • All Rows Identical: The sorting step ensures that the indices are returned in ascending order, maintaining the correct order of weakest rows.