ZeroArray.md

Prompt

Given a 2-Dimensional array (Essentially a grid), write a function that searches for all the values that equal 0 in the array, and then turns all values in the same row and column as the zero into other zeros.

In the event that there are no zeros in the input array, then simply return the input array.

---

Examples

let grid = [
  [1, 1, 1, 1],
  [1, 1, 1, 1],
  [1, 1, 0, 1],
  [1, 1, 1, 1],
];

let grid2 = [
  [1, 1, 1, 1],
  [1, 1, 1, 0],
  [1, 0, 1, 1],
  [1, 1, 1, 1],
];

zeroArray(grid); // should return 
// [
//   [1, 1, 0, 1],
//   [1, 1, 0, 1],
//   [0, 0, 0, 0],
//   [1, 1, 0, 1],
// ];

zeroArray(grid2); // should return 
// [
//   [1, 0, 1, 0],
//   [0, 0, 0, 0],
//   [0, 0, 0, 0],
//   [1, 0, 1, 0],
// ];

---

Hint

It might help to think about what it means to first find the zero(s) within the array, and then somehow keep that value in the form of (rows, columns). (Syntax seems familiar to a 2-D array?)

Solution

Our initial approach will take advantage of our hint, and search for all the zeros in our grid, then go ahead a zero the rows and columns that the zero appears in.

function zeroArray(grid) {
  let rowsToZero = [];
  let columnsToZero = [];
  for (let row = 0; row < grid.length; row++) {
    for (let column = 0; column < grid[row].length; column++) {
      if (grid[row][column] === 0) {
        rowsToZero.push(row);
        columnsToZero.push(column);
      }
    }
  }

  // now rowsToZero and columnsToZero are populated with the items to zero

  let copy = grid;
  rowsToZero.forEach((row) => {
    nullifyRow(copy, row);
  });

  columnsToZero.forEach((column) => {
    nullifyColumn(copy, column);
  });

  return copy;
}

function nullifyRow (grid, row) { // this will set all our rows to 0
  for (let i = 0; i < grid.length; i++) {
    grid[row][i] = 0;
  }
}

function nullifyColumn (grid, column) { // this will set all our columns to 0
  for (let j = 0; j < grid[0].length; j++) {
    grid[j][column] = 0;
  }
}

---

The above solution will have to loop through the entire grid, therefore giving us a time complexity of O(NM), where N would be the number of rows in our grid, and M being the number of columns. Also you'll notice that simply looping through the grid and changing rows and columns to zero as soon as we hit a zero will soon cause a problem. Our entire grid (if a zero is initially present) will turn to 0's!. In order to prevent that from happening, we want to keep a separate index of where all the zeros appear in terms of rows and columns.

Also notice that there is a copy of our input grid halfway through the code. Based on initial conditions that the question sets, this may not be neccessary. If we are allowed to mutate the original input, then we can start modifying the input grid without storing a copy. Otherwise, we will be dealing with O(NM) space for this problem as well.