Minimum Number of Flips to Convert Binary Matrix to Zero Matrix LeetCode solution in JavaScript

1
// Helper counts how many ones are in the matrix to start with. O(mn)
2
var countOnes = function (mat) {
3
  let count = 0;
4
  for (let r = 0; r < mat.length; r++) {
5
    count += mat[r].reduce((a, b) => a + b);
6
  }
7
  return count;
8
};
9

10
// Helper flips a cell and its neighbors. Returns updated number of ones left in matrix. O(1)
11
var flip = function (mat, r, c, numOnes) {
12
  const dirs = [
13
    [0, 1],
14
    [0, -1],
15
    [1, 0],
16
    [-1, 0],
17
    [0, 0],
18
  ];
19
  dirs.forEach((el) => {
20
    let newR = r + el[0],
21
      newC = c + el[1];
22
    if (newR >= 0 && newR < mat.length && newC >= 0 && newC < mat[0].length) {
23
      if (mat[newR][newC] === 0) {
24
        mat[newR][newC] = 1;
25
        numOnes++;
26
      } else {
27
        mat[newR][newC] = 0;
28
        numOnes--;
29
      }
30
    }
31
  });
32
  return numOnes;
33
};
34

35
// Main function tries every possible combination of cells being flipped using backtracking. O (2^(mn))
36
var minFlips = function (mat) {
37
  const rows = mat.length,
38
    cols = mat[0].length;
39
  let minFlips = Infinity,
40
    numOnes = countOnes(mat);
41

42
  var backtrackFlip = function (cell, flips) {
43
    if (numOnes === 0) minFlips = Math.min(minFlips, flips);
44
    for (let newCell = cell; newCell < rows * cols; newCell++) {
45
      // Function uses a cell number instead of row / col to keep track of column flips
46
      // For example, a 2 x 2 grid has cells "0", "1", "2", "3" and the line below calculates row / col based on that number
47
      const r = Math.floor(newCell / cols),
48
        c = newCell % cols;
49
      numOnes = flip(mat, r, c, numOnes);
50
      backtrackFlip(newCell + 1, flips + 1);
51
      numOnes = flip(mat, r, c, numOnes);
52
    }
53
  };
54

55
  backtrackFlip(0, 0);
56
  return minFlips === Infinity ? -1 : minFlips;
57
};