File: the-k-weakest-rows-in-a-matrix/solution.py

Date: 2026-06-06

Time: 19:27

The K Weakest Rows in a Matrix — solution.py

Purpose

This file implements LeetCode #1337. It solves the problem of finding the k rows in a binary matrix that have the fewest soldiers (1s), returning their indices in order from weakest to strongest. It's one solution module among hundreds in this LeetCode implementations repo, following the same single-function-per-file convention.

Key Components

kWeakestRows(mat, k) — The sole public function. Takes a binary matrix and an integer k, returns a list of k row indices sorted ascending by soldier count, with ties broken by row index.

Patterns

The implementation is a single-expression return using a decorate-sort-undecorate (Schwartzian transform) idiom compressed into a list comprehension:

return [i for i, _ in sorted(enumerate(mat), key=lambda x: sum(x[1]))][:k]

Breaking this apart:

1. enumerate(mat) — pairs each row with its index: (0, row0), (1, row1), ...

2. sorted(..., key=lambda x: sum(x[1])) — sorts by the sum of each row (i.e., soldier count). Python's sorted is stable, so rows with equal soldier counts preserve their original index order — which is exactly the tiebreaker the problem requires.

3. [i for i, _ in ...] — extracts just the indices, discarding the rows.

4. [:k] — takes the first k.

This leverages sort stability as the tiebreaker mechanism rather than encoding it explicitly in the key (e.g., key=lambda x: (sum(x[1]), x[0])). Since enumerate produces indices in ascending order and sorted is stable, equal-strength rows naturally stay in index order.

Dependencies

Imports: None — uses only builtins (sorted, enumerate, sum, list slicing).

Imported by: The test_solution.py in the same directory, plus hundreds of other test files across the repo (the "Imported By" list in the prompt appears to be a repo-wide cross-reference artifact, not actual imports of this specific function).

Flow

1. Receive matrix mat and count k.

2. Tag each row with its index.

3. Sort all tagged rows by soldier count (ascending).

4. Strip tags, keeping only indices.

5. Return the first k indices.

Time complexity: O(m·n + m·log(m)) where m = rows, n = columns — O(m·n) to sum every row, O(m·log(m)) to sort.

Space complexity: O(m) for the enumerated/sorted intermediate list.

Invariants

• The input matrix is binary (only 0s and 1s), with all 1s before all 0s in each row. The solution doesn't exploit the sorted-row property — sum(row) works regardless of element order, making it more general than necessary.
• Tiebreaking by row index is guaranteed by sort stability + enumerate producing indices in order.
• k <= m is assumed (per the problem constraints); no bounds checking.

Error Handling

None. The function trusts its inputs per LeetCode's guarantees. Passing k > len(mat) would return fewer than k results (silent truncation via slicing). A non-binary matrix would still work — sum would count total value, not soldier count.