The K Weakest Rows in a Matrix — Problem & Solution
The K Weakest Rows in a Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
The K Weakest Rows in a Matrix is an easy coding problem on arrays, sorting and binary search, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Binary Search, Matrix, Heap
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m × n binary matrix mat of 1s (soldiers) and 0s (civilians). Every row has its soldiers before its civilians.
Row i is weaker than row j if it has fewer soldiers, or if the counts tie and i < j. Return the indices of the k weakest rows, ordered from weakest.
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]
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]
Example 3
Input: mat = [[1,1],[0,0]], k = 1
Output: [1]
Constraints
1 <= mat.length, mat[i].length <= 8Every row is a block of 1s followed by a block of 0s.1 <= k <= mat.length
Hints for The K Weakest Rows in a Matrix
Hint 1
The soldier count of a row is just its sum, since the entries are 0 and 1.
Hint 2
Because each row is sorted, binary search finds the boundary in O(log n) instead of O(n).
Hint 3
Sort by (soldiers, index) so ties break toward the smaller index, then take the first
k.
How to solve The K Weakest Rows in a Matrix
A row's soldier count is its sum; sort row indices by (count, index) and take the first k.
Approach
- Compute each row's sum.
- Sort indices by
(sum, index). - Return the first
k.
Why it works
The composite key encodes the weakness order exactly, with the index as tie-breaker.
Complexity
- Time —
O(m · n + m log m) - Space —
O(m)
Pitfalls
- Since soldiers precede civilians, a binary search per row finds the count in
O(log n); a heap of sizekreplaces the full sort.
Reference solution
Python
def kWeakestRows(mat, k: int):
order = sorted(range(len(mat)), key=lambda i: (sum(mat[i]), i))
return order[:k]Java
public static int[] kWeakestRows(int[][] mat, int k) {
int m = mat.length;
Integer[] order = new Integer[m];
final int[] soldiers = new int[m];
for (int i = 0; i < m; i++) {
int count = 0;
for (int c = 0; c < mat[i].length; c++) count += mat[i][c];
soldiers[i] = count;
order[i] = i;
}
Arrays.sort(order, new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
if (soldiers[a] != soldiers[b]) return soldiers[a] - soldiers[b];
return a - b;
}
});
int[] out = new int[k];
for (int i = 0; i < k; i++) out[i] = order[i];
return out;
}C++
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
vector<pair<int, int>> rows;
for (int i = 0; i < (int) mat.size(); i++) {
int soldiers = 0;
for (int v : mat[i]) soldiers += v;
rows.push_back(make_pair(soldiers, i));
}
sort(rows.begin(), rows.end());
vector<int> out;
for (int i = 0; i < k; i++) out.push_back(rows[i].second);
return out;
}JavaScript
var kWeakestRows = function(mat, k) {
const rows = [];
for (let i = 0; i < mat.length; i++) {
let soldiers = 0;
for (let c = 0; c < mat[i].length; c++) soldiers += mat[i][c];
rows.push([soldiers, i]);
}
rows.sort(function(a, b) { return a[0] !== b[0] ? a[0] - b[0] : a[1] - b[1]; });
const out = [];
for (let i = 0; i < k; i++) out.push(rows[i][1]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms