The K Weakest Rows in a Matrix solution and explanation
Google
9 more videos on this problem
The K Weakest Rows in a Matrix | Live Coding with Explanation | Leetcode - 1337Algorithms Made Easy · 8:06 · 10K views
The K Weakest Rows in a Matrix | Heap + Binary Search | Leetcode 1337 | Day-27Ayushi Sharma · 39:46 · 3K views
Leetcode - The K Weakest Rows in a Matrix (Python)Timothy H Chang · 3:04 · 3K views
3 Ways to Solve 1337. The K Weakest Rows in a Matrix in Python 🐍 | Ace Your Coding Interviews!vanAmsen · 9:24 · 794 views
The K Weakest Rows in a Matrix | LeetCode 1337 | Coders CampCoders Camp · 19:06 · 553 views
The K Weakest Rows in a Matrix | Leetcode 1337 | Array | Binary Search | Max Heap | MatrixNitesh Nanda · 20:19 · 421 views
1337. The K Weakest Rows in a Matrix | Leetcode Easy Level Questions Complete Playlist in PythonEduEverybody · 7:17 · 381 views
The K Weakest Rows in a Matrix | Leetcode 1337 | JavaThe TryIt Project · 12:27 · 341 views
LEETCODE 1337 THE K WEAKEST ROWS IN A MATRIX PYTHON | leetcodeSasa codes · 8:33 · 336 views
1337. The K Weakest Rows in a Matrix (LeetCode)hakunamatasq · 6:08 · 260 views
The problem
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
iis less than the number of soldiers in rowj. - 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.
Example 1:
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].
Example 2:
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.lengthn == mat[i].length2 <= n, m <= 1001 <= k <= mmatrix[i][j]is either 0 or 1.
Approach overview
Problem Overview: You are given a matrix where each row represents soldiers (1s) followed by civilians (0s). A row is weaker if it has fewer soldiers, or if the counts are equal but the row index is smaller. Return the indices of the k weakest rows in ascending order of strength.
Approach 1: Simple Counting and Sorting (Time: O(mn + m log m), Space: O(m))
Iterate through each row and count the number of soldiers by scanning the entire row. Store pairs like (soldierCount, rowIndex) in an array. After processing all rows, sort the array first by soldier count and then by row index. Finally, return the first k indices from the sorted result. This approach relies on straightforward iteration over the array and standard sorting. It is simple to implement and works well when matrix dimensions are small.
Approach 2: Binary Search for Counting (Time: O(m log n + m log m), Space: O(m))
Each row is sorted with all soldiers appearing before civilians. Instead of scanning the entire row, use binary search to find the first 0. The index of that position equals the number of soldiers in the row. Repeat this for every row and store (soldierCount, rowIndex). Sort the pairs and return the first k indices. This reduces the counting step from O(n) per row to O(log n), which is useful when rows are large.
Alternative Optimization: Min Heap / Priority Queue (Time: O(m log n + m log k), Space: O(k))
Instead of sorting all rows, maintain a heap that tracks the k weakest rows seen so far. For each row, compute the soldier count (via binary search or scan) and push the pair into a heap (priority queue). If the heap grows larger than k, remove the strongest element. This avoids sorting the entire list and is more efficient when m is large but k is small.
Recommended for interviews: The binary search counting approach is usually the expected solution because it leverages the sorted row property and improves counting efficiency. Implementing the simple counting version first demonstrates clarity, while adding binary search or a heap shows deeper algorithmic optimization.
Approach 1: Approach 1: Simple Counting and Sorting
In this approach, we directly count the number of soldiers in each row by iterating through the elements of the row, and then sort the rows based on the count followed by their index to determine the order.
Steps to implement:
- Iterate over each row and count the number of soldiers until a 0 is encountered.
- Store the count along with the row index in a list of tuples (or pair structures).
- Sort the list based on the number of soldiers first, and row index as a tiebreaker.
- Extract the top 'k' indices from the sorted list.
from typing import List
def kWeakestRows(mat: List[List[int]], k: int) -> List[int]:
row_strength = []
for index, row in enumerate(mat):
soldier_count = 0
for val in row:
if val == 1:
soldier_count += 1
else:
break
row_strength.append((soldier_count, index))
row_strength.sort()
return [index for _, index in row_strength[:k]]import java.util.*;
class Solution {
public int[] kWeakestRows(int[][] mat, int k) {
int m = mat.length;
int n = mat[0].length;
int[][] strength = new int[m][2];
for (int i = 0; i < m; i++) {
int soldierCount = 0;
for (int j = 0; j < n; j++) {
if (mat[i][j] == 1) {
soldierCount++;
} else {
break;
}
}
strength[i][0] = soldierCount;
strength[i][1] = i;
}
Arrays.sort(strength, Comparator.comparingInt(a -> a[0]));
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = strength[i][1];
}
return result;
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
vector<pair<int, int>> rowStrength;
for (int i = 0; i < mat.size(); ++i) {
int soldierCount = 0;
for (int j = 0; j < mat[i].size(); ++j) {
if (mat[i][j] == 1)
soldierCount++;
else
break;
}
rowStrength.push_back({soldierCount, i});
}
sort(rowStrength.begin(), rowStrength.end());
vector<int> result;
for (int i = 0; i < k; ++i) {
result.push_back(rowStrength[i].second);
}
return result;
}var kWeakestRows = function(mat, k) {
const rowStrength = mat.map((row, index) => {
let soldierCount = 0;
for (let soldier of row) {
if (soldier === 1) soldierCount++;
else break;
}
return [soldierCount, index];
});
rowStrength.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
return rowStrength.slice(0, k).map(pair => pair[1]);
};#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
int *row1 = *(int**)a;
int *row2 = *(int**)b;
return (row1[0] != row2[0]) ? row1[0] - row2[0] : row1[1] - row2[1];
}
int* kWeakestRows(int** mat, int matSize, int* matColSize, int k, int* returnSize) {
int **rowStrength = (int **)malloc(matSize * sizeof(int*));
for (int i = 0; i < matSize; ++i) {
int count = 0;
while (count < *matColSize && mat[i][count] == 1)
count++;
rowStrength[i] = (int *)malloc(2 * sizeof(int));
rowStrength[i][0] = count; // number of soldiers (1s)
rowStrength[i][1] = i; // row index
}
qsort(rowStrength, matSize, sizeof(rowStrength[0]), cmp);
int *weakestRows = (int *)malloc(k * sizeof(int));
for (int i = 0; i < k; ++i)
weakestRows[i] = rowStrength[i][1];
for (int i = 0; i < matSize; ++i)
free(rowStrength[i]);
free(rowStrength);
*returnSize = k;
return weakestRows;
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int[] KWeakestRows(int[][] mat, int k) {
var rowStrength = new List<Tuple<int, int>>();
for (int i = 0; i < mat.Length; i++) {
int soldierCount = 0;
for (int j = 0; j < mat[i].Length; j++) {
if (mat[i][j] == 1) soldierCount++;
else break;
}
rowStrength.Add(new Tuple<int, int>(soldierCount, i));
}
rowStrength.Sort();
return rowStrength.Take(k).Select(x => x.Item2).ToArray();
}
}In the Python solution, a list of tuples is created where each tuple stores the soldier count and the row index. This list is then sorted and the indices of the k weakest rows are extracted.
Time Complexity: O(m*n + m*log m), where the m*n arises from counting soldiers and m*log m from sorting.
Space Complexity: O(m) for storing tuples of soldier counts and indices.
Approach 2: Approach 2: Binary Search for Counting
This approach uses binary search to efficiently count the number of soldiers in each row. Given that soldiers are always positioned before civilians, binary search can help quickly find the first civilian and thus the count of soldiers.
Implementation steps:
- Use binary search on each row to determine the position of the first 0.
- The position found indicates the number of soldiers in that row.
- Store the count along with the row index similarly to approach 1.
- Sort and determine the top 'k' weakest rows as before.
from typing import List
import bisect
def kWeakestRows(mat: List[List[int]], k: int) -> List[int]:
row_strength = []
for index, row in enumerate(mat):
soldier_count = bisect.bisect_right(row, 1)
row_strength.append((soldier_count, index))
row_strength.sort()
return [index for _, index in row_strength[:k]]import java.util.*;
class Solution {
private int countSoldiers(int[] row) {
int low = 0;
int high = row.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (row[mid] == 1) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
public int[] kWeakestRows(int[][] mat, int k) {
int[][] strength = new int[mat.length][2];
for (int i = 0; i < mat.length; i++) {
int soldierCount = countSoldiers(mat[i]);
strength[i][0] = soldierCount;
strength[i][1] = i;
}
Arrays.sort(strength, Comparator.comparingInt(a -> a[0]));
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = strength[i][1];
}
return result;
}
}#include <vector>
#include <algorithm>
using namespace std;
int countSoldiers(const vector<int>& row) {
int low = 0, high = row.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (row[mid] == 1) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
vector<pair<int, int>> rowStrength;
for (int i = 0; i < mat.size(); ++i) {
int soldierCount = countSoldiers(mat[i]);
rowStrength.push_back({soldierCount, i});
}
sort(rowStrength.begin(), rowStrength.end());
vector<int> result;
for (int i = 0; i < k; ++i) {
result.push_back(rowStrength[i].second);
}
return result;
}const kWeakestRows = function(mat, k) {
const binarySearch = (row) => {
let low = 0, high = row.length - 1;
while (low <= high) {
const mid = Math.floor((low + high) / 2);
if (row[mid] === 1) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
};
const rowStrength = mat.map((row, index) => [binarySearch(row), index]);
rowStrength.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
return rowStrength.slice(0, k).map(pair => pair[1]);
};#include <stdio.h>
#include <stdlib.h>
int binarySearch(int* row, int n) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (row[mid] == 1) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}
int cmp(const void *a, const void *b) {
int *row1 = *(int**)a;
int *row2 = *(int**)b;
return (row1[0] != row2[0]) ? row1[0] - row2[0] : row1[1] - row2[1];
}
int* kWeakestRows(int** mat, int matSize, int* matColSize, int k, int* returnSize) {
int **rowStrength = (int **)malloc(matSize * sizeof(int*));
for (int i = 0; i < matSize; ++i) {
int count = binarySearch(mat[i], *matColSize);
rowStrength[i] = (int *)malloc(2 * sizeof(int));
rowStrength[i][0] = count;
rowStrength[i][1] = i;
}
qsort(rowStrength, matSize, sizeof(rowStrength[0]), cmp);
int *weakestRows = (int *)malloc(k * sizeof(int));
for (int i = 0; i < k; ++i)
weakestRows[i] = rowStrength[i][1];
for (int i = 0; i < matSize; ++i)
free(rowStrength[i]);
free(rowStrength);
*returnSize = k;
return weakestRows;
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
private int CountSoldiers(int[] row) {
int low = 0, high = row.Length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (row[mid] == 1)
low = mid + 1;
else
high = mid - 1;
}
return low;
}
public int[] KWeakestRows(int[][] mat, int k) {
var rowStrength = new List<Tuple<int, int>>();
for (int i = 0; i < mat.Length; i++) {
int soldierCount = CountSoldiers(mat[i]);
rowStrength.Add(new Tuple<int, int>(soldierCount, i));
}
rowStrength.Sort();
return rowStrength.Take(k).Select(x => x.Item2).ToArray();
}
}The use of Python's bisect module allows for direct computation of soldiers count using binary search, followed by sorting the constructed pairs as in prior examples.
Time Complexity: O(m*log n + m*log m), attributed to binary search method efficiency in counting soldiers.
Space Complexity: O(m), manifest in the storage of computed row strengths.
Approach 3: Default Approach
function kWeakestRows(mat: number[][], k: number): number[] {
let n = mat.length;
let sumMap = mat.map((d, i) => [d.reduce((a, c) => a + c, 0), i]);
let ans = [];
// 冒泡排序
for (let i = 0; i < k; i++) {
for (let j = i; j < n; j++) {
if (
sumMap[j][0] < sumMap[i][0] ||
(sumMap[j][0] == sumMap[i][0] && sumMap[i][1] > sumMap[j][1])
) {
[sumMap[i], sumMap[j]] = [sumMap[j], sumMap[i]];
}
}
ans.push(sumMap[i][1]);
}
return ans;
}func kWeakestRows(mat [][]int, k int) []int {
m, n := len(mat), len(mat[0])
res := make([]int, m)
var idx []int
for i, row := range mat {
idx = append(idx, i)
left, right := 0, n
for left < right {
mid := (left + right) >> 1
if row[mid] == 0 {
right = mid
} else {
left = mid + 1
}
}
res[i] = left
}
sort.Slice(idx, func(i, j int) bool {
return res[idx[i]] < res[idx[j]] || (res[idx[i]] == res[idx[j]] && idx[i] < idx[j])
})
return idx[:k]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Simple Counting and Sorting | Time Complexity: O(m*n + m*log m), where the m*n arises from counting soldiers and m*log m from sorting. Space Complexity: O(m) for storing tuples of soldier counts and indices. |
| Approach 2: Binary Search for Counting | Time Complexity: O(m*log n + m*log m), attributed to binary search method efficiency in counting soldiers. Space Complexity: O(m), manifest in the storage of computed row strengths. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting + Sorting | O(mn + m log m) | O(m) | Best for simple implementation when matrix size is small |
| Binary Search + Sorting | O(m log n + m log m) | O(m) | When rows are sorted and you want faster soldier counting |
| Binary Search + Heap | O(m log n + m log k) | O(k) | Useful when number of rows is large but only k weakest are needed |
Frequently asked questions
Is The K Weakest Rows in a Matrix easy or hard?
The K Weakest Rows in a Matrix is classified as an Easy problem on LeetCode with a high acceptance rate. The core idea involves counting soldiers in each row and sorting, while binary search provides a small optimization for larger inputs.
The K Weakest Rows in a Matrix Python/Java solution
Python and Java solutions typically compute soldier counts using either a loop or binary search, store pairs of (count, index), and then sort them. Python often uses tuples and the built-in sort, while Java commonly uses arrays with a custom comparator or a priority queue.
How to solve The K Weakest Rows in a Matrix in O(m log n)?
Use binary search on every row to locate the first 0, which directly gives the soldier count. This takes O(log n) per row, so counting across m rows costs O(m log n). Then use a heap of size k or sorting to determine the k weakest rows.
What is the best approach for The K Weakest Rows in a Matrix?
Binary search combined with sorting or a heap is the most efficient approach. Because each row contains soldiers (1s) followed by civilians (0s), binary search can find the soldier count in O(log n) time. After computing counts for all rows, sort them or maintain a heap to extract the k weakest rows.
Is The K Weakest Rows in a Matrix asked at Google/Amazon/Meta?
This problem appears frequently in coding interview practice sets and is commonly associated with companies like Amazon and Google. It tests basic matrix processing, sorting, and binary search optimization, which are common interview topics.
What data structure is used in The K Weakest Rows in a Matrix?
Typical solutions use arrays to store (soldierCount, rowIndex) pairs and apply sorting. Optimized implementations may use binary search for counting and a heap or priority queue to track the k weakest rows efficiently.
What is the time complexity of The K Weakest Rows in a Matrix?
The straightforward solution scans each row and sorts the results, giving O(mn + m log m) time. Using binary search reduces counting to O(m log n), and sorting adds O(m log m). A heap optimization can reduce sorting overhead to O(m log k).