0

I built the Set Matrix Zeroes algorithm in JavaScript. I have a lot of loops in my code, so was wondering if there is a better way to implement this algorithm.

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

I loop the matrix and when I find a 0, I set its entire row and column to a flag ('X'). I do not set 'X' if the position is a 0 because I might need to check this position in the future. At the end I replace all the 'X' to 0.

var setZeroes = function(matrix) {
    if(matrix === null || matrix.length === 0)
        return [];
    
    for(let i=0; i<matrix.length; i++){
        for(let j=0; j<matrix[i].length; j++){
            if(matrix[i][j] === 0){
                setFlag(matrix, i, j);
            }
        }
    }
    
    for(i=0; i<matrix.length; i++){
        for(j=0; j<matrix[i].length; j++){
            if(matrix[i][j] === 'X')
                matrix[i][j] = 0;
        }
    }
};

const setFlag = function(matrix, i, j) {
    matrix[i][j] = 'X';
    let tempI = i+1;
    while(tempI < matrix.length){
        if(matrix[tempI][j] !== 0)
            matrix[tempI][j] = 'X';
        tempI++;
    }
    tempI = i-1;
    while(tempI >= 0){
        if(matrix[tempI][j] !== 0)
            matrix[tempI][j] = 'X';
        tempI--;
    }
    let tempJ = j+1;
    while(tempJ < matrix[i].length){
        if(matrix[i][tempJ] !== 0)
            matrix[i][tempJ] = 'X';
        tempJ++;
    }
    tempJ = j-1;
    while(tempJ >= 0){
        if(matrix[i][tempJ] !== 0)
            matrix[i][tempJ] = 'X';
        tempJ--;
    }
}
myTest532 myTest532
  • 2,091
  • 3
  • 35
  • 78

3 Answers3

1

Here is a more declarative implementation which Jsperf prefers by a decent margin.

let replaceRowCol = (matrix, trg=0, val=0) => {
  
  // Store width and height of matrix
  let w = matrix.length;
  let h = matrix[0].length;
  
  // An array to hold all replacements that need to be made
  let replaceArr = [];
  
  // Any coord whose value is `trg` results in a replacement at that coord
  for (let x = 0; x < w; x++) { for (let y = 0; y < h; y++) {
    if (matrix[x][y] === trg) replaceArr.push({ x, y });
  }}
  
  // Perform all replacements
  for (let { x, y } of replaceArr) {
    for (let xx = 0; xx < w; xx++) matrix[xx][y] = val;
    for (let yy = 0; yy < h; yy++) matrix[x][yy] = val;
  }
  
  return matrix;
  
};

let matrix = replaceRowCol([
  [ 0, 2, 3, 4 ],
  [ 1, 2, 3, 4 ],
  [ 1, 2, 0, 4 ],
  [ 1, 2, 3, 4 ]
]);

for (let row of matrix) console.log(row.join(' '));

Instead of inserting temporary placeholder values into the matrix, this approach performs a first-pass to remember the locations of all zeroes, and a second pass over these memorized locations to replace the rows and cols.

The speed is a result of avoiding callbacks and function calls, with the exception of Array.prototype.push (and note this could be avoided if we used a simple linked list instead). Even though callbacks get compiled and are very quick under any decent javascript VM, they still aren't as fast as good old procedural code, like the above.

It's worth mentioning the possibility for a very cheeky speedup: if multiple rows need to be replaced, you could set every item in the first such row to zeroes, but for every row after, you could reference the first zeroed row. This would entirely skip the need to iterate later rows. Of course, the resulting matrix would have multiple rows that are all references to the same array, which could lead to highly unexpected results during future operations.

This cheeky speedup would look something like this:

let replacedX = null;
for (let { x, y } of replaceArr) {
  // We still need to replace the column, as usual
  for (let xx = 0; xx < w; xx++) matrix[xx][y] = val;
  if (replacedX === null) {
    replacedX = matrix[x] = Array(w).fill(val); // This has O(w) runtime
  } else {
    matrix[x] = replacedX;                      // This has O(1) runtime
  }
}

EDIT: Linked list implementation. It's included in the jsperf, and it's a bit faster!

let replaceRowColLinkedList = (matrix, trg=0, val=0) => {
  
  // Store width and height of matrix
  let w = matrix.length;
  let h = matrix[0].length;
  
  // A linked list
  let replacements = null;
  
  // Any coord whose value is `trg` results in a replacement at that coord
  for (let x = 0; x < w; x++) { for (let y = 0; y < h; y++) {
    if (matrix[x][y] === trg) {
      let next = replacements;
      replacements = { x, y, next };
    }
  }}
  
  // Perform all replacements
  let llNode = replacements;
  while (llNode) {
    let { x, y, next } = llNode;
    for (let xx = 0; xx < w; xx++) matrix[xx][y] = val;
    for (let yy = 0; yy < h; yy++) matrix[x][yy] = val;
    llNode = next;
  }
  
  return matrix;
  
};

let matrix = replaceRowColLinkedList([
  [ 0, 2, 3, 4 ],
  [ 1, 2, 3, 4 ],
  [ 1, 2, 0, 4 ],
  [ 1, 2, 3, 4 ]
]);

for (let row of matrix) console.log(row.join(' '));

EDIT: For large matrices with many collisions (many zeroes which share the same row or column) it may be worth using Set to avoid re-zeroing rows/cols. The downside, of course, is that Set.prototype.add must have a runtime worse than O(1), regardless of implementation. Overall, however, the runtime of Set.prototype.add is negligible for smaller matrices, and for larger matrices there can be significant benefits from avoiding collisions. This method is consistently fastest in the jsperf, and the method I overall recommend!

let replaceRowCol = (matrix, trg=0, val=0) => {
  
  // Store width and height of matrix
  let w = matrix.length;
  let h = matrix[0].length;
  
  // Store columns and rows to replace
  let replaceX = new Set();
  let replaceY = new Set();
  
  // Any coord whose value is `trg` results in a replacement at that coord
  for (let x = 0; x < w; x++) { for (let y = 0; y < h; y++) {
    if (matrix[x][y] === trg) {
      replaceX.add(x);
      replaceY.add(y);
    }
  }}
  
  // Perform all replacements
  for (let x of replaceX) for (let y = 0; y < h; y++) matrix[x][y] = val;
  for (let y of replaceY) for (let x = 0; x < w; x++) matrix[x][y] = val;
  
  return matrix;
  
};

let matrix = replaceRowCol([
  [ 0, 2, 3, 4, 5, 6 ],
  [ 1, 2, 3, 4, 5, 6 ],
  [ 1, 2, 3, 4, 5, 6 ],
  [ 1, 2, 3, 0, 5, 6 ],
  [ 1, 2, 3, 4, 5, 6 ]
]);

for (let row of matrix) console.log(row.join(' '));
Gershom Maes
  • 7,358
  • 2
  • 35
  • 55
0

Simple approach, if you want to use more features in js.

cols = []
matrix = matrix.map(row => {
    cols.push(...row.reduce((a, v, i) => (v == 0 && a.push(i), a), []) )
    return row.includes(0) ? Array(row.length).fill(0) : row;
})

then you have a list of all the columns you need to replace in the "cols" array. just loop over that and set to zero like so:

cols.forEach((i) => {
    matrix = matrix.map(row => row.map((v, idx) => i == idx ? 0 : v))
})

Working example:

let matrix = [
  [ 1, 2, 3, 4, 5 ],
  [ 1, 0, 3, 4, 5 ],
  [ 1, 2, 3, 4, 0 ],
  [ 1, 2, 3, 4, 5 ],
  [ 1, 2, 3, 4, 5 ]
];


cols = []
matrix = matrix.map(row => {
  cols.push(...row.reduce((a, v, i) => (v == 0 && a.push(i), a), []) )
  return row.includes(0) ? Array(row.length).fill(0) : row;
})

cols.forEach((i) => {
    matrix = matrix.map(row => row.map((v, idx) => i == idx ? 0 : v))
})

for (let row of matrix) console.log(row.join(' '));
Gershom Maes
  • 7,358
  • 2
  • 35
  • 55
tm2josep
  • 599
  • 5
  • 10
  • I believe there are 2 mistakes here: your reducer always needs to return `a`, and your reducer's initial value should be `[]`. The line should be: `cols.push( ...row.reduce((a, v, i) => (v == 0 && a.push(i), a), []));`. Otherwise your code is broken, saying you have a non-callable iterator (because the result of `reduce` isn't an array) – Gershom Maes Jun 29 '20 at 16:46
  • I wrote it without testing, on my phone. You're right thought, good catch – tm2josep Jun 30 '20 at 17:37
0
let arr = [
  [1, 0, 1],
  [8, 8, 4],
  [2, 8, 7],
];
let len= arr.length;
const matrixZero = (arr, len) => {
  let left = 0;
  let right = len - 1;
  let top = 0;
  let down = len - 1;
  const M = len,
   N = len;
  var arr1 = Array.from(Array(M), () => new Array(N));
  while (top <= down) {
    for (let i = left; i <= right; i++) {
      if (arr[top][i] == 0) {
        arr1[top][i] = true;
      }
    }
    top++;
  }
  top = 0;
  while (top <= down) {
    for (let i = left; i <= right; i++) {
      if (arr1[top][i] == true) {
        delrow(top, arr);
        delcol(i, arr);
      }
    }
    top++;
  }

 return arr
};
const delrow = (in1, arr) => {
  for (let i = 0; i < arr.length; i++) {
    arr[in1][i] = 0;
  }
  return arr;
};
const delcol = (in2, arr) => {
  for (let j = 0; j < arr.length; j++) {
    arr[j][in2] = 0;
  }
  return arr
};
console.log(matrixZero(arr, len));
ritik bhatt
  • 11
  • 2