This is one of the easy problems in LeeteCode. solution But my question isn't really about the problem, the code bellow iterate through a 2d Array like this
[
[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],
]
The problem, I don't understand is why j <= x while i < y isn't j going an extra iteration? I would have thought j < would be the correct way but it is not
var kWeakestRows = function(M, K) {
let y = M.length, x = M[0].length,
vis = new Uint8Array(y), ans = []
for (let j = 0; j <= x; j++)
for (let i = 0; i < y; i++) {
if (!vis[i] && !M[i][j]) ans.push(i), vis[i]++
if (ans.length === K) return ans
}
};
It's a trick to simplify writing the condition that checks how many soldiers are in a row.
It simplifies the code (as in : the number of characters you type), it certainly doesn't simplify the comprehension, and one should probably test how the performance is impacted.
You will note that each row has x cells, but the "number of soldiers" of a row can be any value in [0, x], and that's x+1 possible values.
Let's write a simpler function which just checks what rows have "at most j soldiers" :
func checkAtMost(M, j) {
let y = M.length, x = M[0].length;
// if you want to avoid accessing out of bound cells, you have to
// compare 'j' to 'x' :
for (let i = 0; i <= y; j++)
if (j >= x || !M[i][j]) {
console.log("row "+i+" has at most "+j+" soldiers");
}
}
but javascript's specifications say :
undefinedundefined is converted to false when used in a boolean expressionso actually, when j >= x evaluates to true : M[i][j] == undefined, and !M[i][j] also evaluates to true.
Therefore, the above function is equivalent to :
func checkAtMost(M, j) {
let y = M.length;
// who cares about bounds ? we're writing javascript !
for (let i = 0; i <= y; i++)
if (!M[i][j]) {
console.log("row "+i+" has at most "+j+" soldiers");
}
}
and that's a way to have it work for any of j in [0,x] (x+1 values) even though each row has only x cells.
note that the suggested python solution does have the bound checking :
if not vis[i] and (j == x or not M[i][j]):
...
I think I've got it. j is the index of an element across a row - so by the time j reaches x, i.e., all elements in the matrix have been iterated over, the answer should have been found.
If you've followed the algorithm mentioned, you know that it iterates over each row for each column, in this order. So the algorithm finishes with the final column and iterates over each row index. When it finishes this iteration, j goes from x-1 to x. Since K is guaranteed to be equal to or less than y, ans.length will definitely be K by this point, and the return statement will execute.
j will reach the value of x if and only if K is equal to the number of rows in the matrix i.e., the maximum possible number of outputs that can be given for the given matrix.
Alternative approach:
You can calculate the soldiers count for each row and then sort the rows by their soldiers count and resolve ties based on the index.
var kWeakestRows = function (M, K) {
const soldiers = M.map((row, i) => [row.reduce((total, r) => total + r), i]);
return soldiers
.sort(([aCnt, aIdx], [bCnt, bIdx]) => {
if (aCnt === bCnt) return aIdx - bIdx;
else return aCnt - bCnt;
})
.map(([, i]) => i)
.slice(0, K);
};
kWeakestRows(
[
[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],
],
3
);