The K Weakest Rows in a Matrix

Easy
284.

The K Weakest Rows in a Matrix

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.

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 <= 8
  • Every row is a block of 1s followed by a block of 0s.
  • 1 <= k <= mat.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number[]}
 */
var kWeakestRows = function(mat, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 8
  • Every 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

  1. Hint 1

    The soldier count of a row is just its sum, since the entries are 0 and 1.

  2. Hint 2

    Because each row is sorted, binary search finds the boundary in O(log n) instead of O(n).

  3. 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

  1. Compute each row's sum.
  2. Sort indices by (sum, index).
  3. 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 size k replaces 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