1337. The K Weakest Rows in a Matrix

Solution

  • Count the soldiers in each row;
  • For each row save the number of soldiers and the row index;
  • Sort the array by soldiers and then by index;
  • Pick only the k weakest row.
/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number[]}
 */
var kWeakestRows = function(mat, k) {
    let s = []; // [sodiers, index]
    
    // Count soldiers
    for (let i = 0; i < mat.length; i++) {
        s[i] = [mat[i].reduce((p, c) => p + c, 0), i];
    }
    
    // Sort array
    s = s.sort((a, b) => {
        if (a[0] !== b[0]) {
            return a[0] - b[0];
        } else {
            return a[1] - b[1];
        }
    });
    
    // Pick only the k weakest rows
    const result = [];
    for (let i = 0; i < k; i++) {
        result.push(s[i][1]);
    }
    
    return result;
};

My solution is quite naive. I found a better one here:

/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number[]}
 */
var kWeakestRows = function(mat, k) {
    let y = mat.length;
    let x = mat[0].length;
    let vis = new Uint8Array(y);
    let ans = [];

    for (let j = 0; j <= x; j++) {
        for (let i = 0; i < y; i++) {
            if (!vis[i] && !mat[i][j]) {
                ans.push(i), vis[i]++;
            }
            if (ans.length === k) {
                return ans;
            }
        }
    }
};

Complexity

  • Time Complexity: O(m*nlog(n+k)).
  • Space Complexity: O(m).

All Solutions