Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1337. The K Weakest Rows in a Matrix - Leetcode Solution

Code Implementation

class Solution:
    def kWeakestRows(self, mat, k):
        # Count soldiers in each row (sum of 1s)
        row_strength = [(sum(row), idx) for idx, row in enumerate(mat)]
        # Sort by number of soldiers, then by row index
        row_strength.sort()
        # Return indices of the k weakest rows
        return [idx for _, idx in row_strength[:k]]
      
class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        vector<pair<int, int>> strength;
        for (int i = 0; i < mat.size(); ++i) {
            int soldiers = accumulate(mat[i].begin(), mat[i].end(), 0);
            strength.push_back({soldiers, i});
        }
        sort(strength.begin(), strength.end());
        vector<int> result;
        for (int i = 0; i < k; ++i) {
            result.push_back(strength[i].second);
        }
        return result;
    }
};
      
class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        int m = mat.length;
        int[][] strength = new int[m][2];
        for (int i = 0; i < m; i++) {
            int soldiers = 0;
            for (int val : mat[i]) soldiers += val;
            strength[i][0] = soldiers;
            strength[i][1] = i;
        }
        Arrays.sort(strength, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = strength[i][1];
        }
        return result;
    }
}
      
var kWeakestRows = function(mat, k) {
    let strength = mat.map((row, idx) => [row.reduce((a, b) => a + b, 0), idx]);
    strength.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    return strength.slice(0, k).map(pair => pair[1]);
};

Problem Description

Given a binary matrix mat with m rows and n columns, where each row represents soldiers (1) followed by civilians (0), the task is to find the indices of the k weakest rows in the matrix. The "weakness" of a row is defined by the number of soldiers in it. If two rows have the same number of soldiers, the row with the lower index is considered weaker. The output should be a list of k row indices, sorted from weakest to strongest.

Thought Process

To solve this problem, we need to compare each row based on the number of soldiers it contains. Since all soldiers are always to the left of civilians in a row, the count of 1s in each row gives us the strength of that row. The brute-force approach would be to count soldiers in every row, sort all rows by their soldier count (and row index for ties), and return the indices of the first k rows. If we want to optimize, we could use a priority queue to keep track of the k weakest rows as we process each one, but since the constraints are reasonable, sorting is simple and efficient enough.

Solution Approach

The solution can be broken down into clear steps:
  • Step 1: For each row in mat, count the number of soldiers (1s). Since all 1s come before 0s, this can be done by summing the row.
  • Step 2: Pair each row's soldier count with its index. This allows us to keep track of which row has which strength.
  • Step 3: Sort all the pairs. The sorting should prioritize the soldier count first (ascending), then row index (ascending) for tie-breaking.
  • Step 4: Extract the indices of the first k pairs from the sorted list. These represent the k weakest rows.
This approach is simple and leverages built-in sorting for clarity and efficiency. If you want to optimize further, you could use binary search to count soldiers in each row (since rows are sorted), but for most practical inputs, the difference is minor.

Example Walkthrough

Consider the following 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
Step-by-step:
  1. Count soldiers in each row:
    • Row 0: 2 soldiers
    • Row 1: 4 soldiers
    • Row 2: 1 soldier
    • Row 3: 2 soldiers
    • Row 4: 5 soldiers
  2. Pair with indices: [(2,0), (4,1), (1,2), (2,3), (5,4)]
  3. Sort by soldiers, then index: [(1,2), (2,0), (2,3), (4,1), (5,4)]
  4. Take first 3 indices: [2,0,3]
So, the output is [2, 0, 3].

Time and Space Complexity

  • Brute-force: Counting soldiers in each row takes O(n) per row, so O(mn) total. Sorting the m rows takes O(m log m). So overall, O(mn + m log m) time and O(m) space for storing the pairs.
  • Optimized: If we use binary search to count soldiers (since rows are sorted), counting per row becomes O(log n), so total O(m log n + m log m). However, for typical constraints, the simpler O(mn + m log m) is often sufficient and easier to write.

Summary

The problem asks us to find the k weakest rows in a matrix by counting soldiers in each row and sorting them. The key insights are to pair each row's soldier count with its index, sort by those criteria, and extract the indices of the weakest rows. The solution is efficient, leverages built-in language features, and is easy to understand, making it both elegant and practical for real-world use.