Shifting all zeros in column matrix to the end

user_9821034 0
Viewed 86

I have the following matrix 

var matrix = [
    [2,    0,    0,  2],
    [4,    0,    0,  2],
    [2,    64,   32, 4],
    [1024, 1024, 64, 0]
];

And I would like to shift the zeros in the second and third column of first and second row to the end, but I don't know how to do it. Here is my attempt:

for(var i = 0; i < matrix.length; i++) {
    for(var j = 0; j < matrix.length ;j++) {
        //push zeroes to the end
        if(matrix[j][i] === 0){
            for(var k = j+1; k<2;k++){
                matrix[j][i] = matrix[k][i]
            }
            matrix[3][i] = 0
        }
    }
}

This is what it returns vs. what I expected:

Returns:  [[2, 0,  0,  2], [4, 0,    0,  2], [2, 64, 32, 4], [1024, 0, 0, 0]]
Expected: [[2, 64, 32, 2], [4, 1024, 64, 2], [2, 0,  0,  4], [1024, 0, 0, 0]]

I would really appreciate any help

javascript
3 Answers

To shift zeros on each column, your can transpose the matrix, shift each row and transpose it back:

let zip = a => a[0].map((_, i) => a.map(b => b[i]))

let shiftZeros = a => a.filter(x => x).concat(a.filter(x => !x))

//

let matrix = [
    [2,    0,    0,  2],
    [4,    0,    0,  2],
    [2,    64,   32, 4],
    [1024, 1024, 64, 0]
];

result = zip(zip(matrix).map(shiftZeros))

console.log(result.map(x => x.join()))

user_9891210

Here you go:

function shift(m) {
  const length = m.length;
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length; j++) {
      if (m[i][j] === 0) {
        for (let ni = i + 1; ni < length; ni++) {
          if (m[ni][j] !== 0) {            
            [m[i][j], m[ni][j]] = [m[ni][j], m[i][j]];
            break;
          }
        }
      }
    }
  }
  return m;
}

var matrix = [[2,    0,    0,  2],
              [4,    0,    0,  2],
              [2,    64,   32, 4],
              [1024, 1024, 64, 0]];

console.log(shift(matrix).map(a => a.map(n => String(n).padStart(5, " "))).join("\n"))

user_56644340

The approach presented is a bit unclear since some rows are hardcoded, but it does look like a triply nested loop. This will run in O(n3) time unnecessarily.

An efficient approach is to use two pointers--one pointing to the swap location for the next zero per column and one pointing to the current element. After finishing traversal of a column, zero out everything after the swap pointer. This runs in O(n2) time (we visit each element in the matrix once).

const zeroesToColEnd = matrix => {
  for (let col = 0; col < matrix.length; col++) {
    let i = 0;

    for (const row of matrix) {
      if (row[col]) {
        matrix[i++][col] = row[col];
      }
    }

    for (; i < matrix.length; matrix[i++][col] = 0);
  }
  
  return matrix;
};

const matrix = [[2,    0,    0,  2],
                [4,    0,    0,  2],
                [2,    64,   32, 4],
                [1024, 1024, 64, 0]];
const print = m => m.map(row => row.map(e => ("" + e).padStart(4, " ")).join("|")).join("\n");
console.log(print(zeroesToColEnd(matrix)));

user_62433520
Related