Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Hard Graphs BFS for shortest path Original on LeetCode

Reported atAirbnb

Minimum Number of Flips to Convert Binary Matrix to Zero Matrix is a hard graphs problem solved with the bfs for shortest path pattern. The best approach, optimal (choose the first row, the rest is forced), runs in O(2^n · m · n) time and O(m · n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every set of cells) up.

Problem

You are given an m x n binary matrix mat. In one move you pick a cell and flip it together with each of its up to four edge-adjacent neighbours: every 0 among them becomes 1 and every 1 becomes 0.

Return the minimum number of moves needed to turn mat into a matrix of all zeros, or -1 if that is impossible.

Examples

Example 1

Input
mat = [[1, 0, 1]]
Output
2
Why
Flipping the left cell gives [0, 1, 1]; flipping the right cell then clears the last two cells.

Example 2

Input
mat = [[1, 0], [0, 0]]
Output
3
Why
Flipping the top-left, top-right and bottom-left cells toggles the top-left cell three times and every other cell exactly twice, leaving only zeros. No shorter sequence works.

Example 3

Input
mat = [[0, 1]]
Output
-1
Why
In a 1 x 2 grid every flip toggles both cells, so the two cells can never both become 0.

Constraints

  • 1 <= m, n <= 3, where m and n are the numbers of rows and columns
  • mat[i][j] is 0 or 1

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 16 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (try every set of cells)O(2^(mn) · mn)O(mn)
BFS over grid statesO(2^(mn) · mn)O(2^(mn))
Optimal (choose the first row, the rest is forced)O(2^n · m · n)O(m · n)

1Brute force (try every set of cells)

TimeO(2^(mn) · mn)2^(mn) subsets, each applying up to mn toggles (at most 512 · 9 here).
SpaceO(mn)The toggle masks.

Because flips commute and flipping a cell twice cancels out, any solution is a subset of cells flipped once each. Encode the grid as a bit mask and, for each cell, the mask of cells its flip toggles. For every subset, XOR the start state with the masks of the chosen cells; if the result is 0, the subset size is a candidate.

  1. Encode mat as start, bit i * n + j for cell (i, j).
  2. For each cell build toggle[c]: the cell and its existing neighbours.
  3. For every subset of the m·n cells, XOR start with the chosen toggles; if it becomes 0, keep the smallest subset size.
  4. Return that size, or -1 if no subset works.
class Solution {
    public int minFlips(int[][] mat) {
        int m = mat.length, n = mat[0].length, cells = m * n;
        int start = 0;
        int[] toggle = new int[cells];
        int[][] dirs = { { 0, 0 }, { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) start |= 1 << (i * n + j);
                for (int[] d : dirs) {
                    int r = i + d[0], c = j + d[1];
                    if (r >= 0 && r < m && c >= 0 && c < n) toggle[i * n + j] |= 1 << (r * n + c);
                }
            }
        }
        int best = -1;
        for (int subset = 0; subset < (1 << cells); subset++) {
            int state = start;
            for (int c = 0; c < cells; c++) {
                if ((subset >> c & 1) == 1) state ^= toggle[c];
            }
            if (state == 0) {
                int size = Integer.bitCount(subset);
                if (best == -1 || size < best) best = size;
            }
        }
        return best;
    }
}

2BFS over grid states

TimeO(2^(mn) · mn)Each of the 2^(mn) states is expanded once with mn possible flips, but BFS can stop early as soon as it reaches 0.
SpaceO(2^(mn))The distance array and queue over all states.

View every possible grid as a node (a bit mask of at most 9 bits) and every single flip as an edge. The fewest flips is the shortest path from the start mask to 0, which BFS finds level by level. If BFS runs out of states without reaching 0, the target is unreachable.

  1. Encode the grid and the toggle masks as in the brute force.
  2. BFS from start with a dist array of size 2^(mn) filled with -1.
  3. Pop a state; if it is 0 return its distance; otherwise push state ^ toggle[c] for every unvisited neighbour.
  4. Return -1 when the queue empties.
class Solution {
    public int minFlips(int[][] mat) {
        int m = mat.length, n = mat[0].length, cells = m * n;
        int start = 0;
        int[] toggle = new int[cells];
        int[][] dirs = { { 0, 0 }, { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) start |= 1 << (i * n + j);
                for (int[] d : dirs) {
                    int r = i + d[0], c = j + d[1];
                    if (r >= 0 && r < m && c >= 0 && c < n) toggle[i * n + j] |= 1 << (r * n + c);
                }
            }
        }
        int[] dist = new int[1 << cells];
        Arrays.fill(dist, -1);
        dist[start] = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int state = queue.poll();
            if (state == 0) return dist[state];
            for (int c = 0; c < cells; c++) {
                int next = state ^ toggle[c];
                if (dist[next] == -1) {
                    dist[next] = dist[state] + 1;
                    queue.add(next);
                }
            }
        }
        return -1;
    }
}

3Optimal (choose the first row, the rest is forced)

TimeO(2^n · m · n)2^n first-row choices, each followed by one forced pass over the grid (each flip touches 5 cells).
SpaceO(m · n)One working copy of the grid.

Decide only which cells of the first row to flip (2^n choices). After that, a 1 left in row r - 1 can only be cleared by flipping the cell directly below it, since every other cell that touches it has already been decided. So walk down the rows flipping exactly those cells, and the choice is valid if the last row ends up all zero. Keep the smallest count over all first-row choices.

  1. For each mask over the n columns: copy the grid, flip the first-row cells in the mask and count them.
  2. For r = 1..m-1 and every column c: if grid[r-1][c] == 1, flip (r, c) and count it.
  3. If the last row is all zero, update the best count.
  4. Return the best count, or -1 if no mask worked.
class Solution {
    public int minFlips(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int best = -1;
        for (int mask = 0; mask < (1 << n); mask++) {
            int[][] g = new int[m][];
            for (int i = 0; i < m; i++) g[i] = mat[i].clone();
            int count = 0;
            for (int c = 0; c < n; c++) {
                if ((mask >> c & 1) == 1) { flip(g, 0, c); count++; }
            }
            for (int r = 1; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    if (g[r - 1][c] == 1) { flip(g, r, c); count++; }
                }
            }
            boolean clear = true;
            for (int c = 0; c < n; c++) if (g[m - 1][c] == 1) clear = false;
            if (clear && (best == -1 || count < best)) best = count;
        }
        return best;
    }

    private void flip(int[][] g, int r, int c) {
        int m = g.length, n = g[0].length;
        g[r][c] ^= 1;
        if (r > 0) g[r - 1][c] ^= 1;
        if (r + 1 < m) g[r + 1][c] ^= 1;
        if (c > 0) g[r][c - 1] ^= 1;
        if (c + 1 < n) g[r][c + 1] ^= 1;
    }
}

Edge cases to test

  • The matrix is already all zeros (answer 0)
  • Grids where no sequence works (answer -1), such as 1 x 2 or some 2 x 3 patterns
  • A single cell
  • The all-ones 3 x 3 grid, which needs many flips

Hints

Hint 1

Flipping the same cell twice changes nothing, and the order of flips does not matter. So an answer is just a set of cells, each flipped once.

Hint 2

With at most 9 cells there are at most 2^9 sets: you can try them all. Alternatively, treat each grid as a 9-bit state and run BFS from the start state to the all-zero state.

Hint 3

Faster still: once you choose the flips in the first row, every later flip is forced, because the only way left to clear a 1 in row r - 1 is to flip the cell right below it.

FAQ

What is the best time complexity for Minimum Number of Flips to Convert Binary Matrix to Zero Matrix?

Optimal (choose the first row, the rest is forced) runs in O(2^n · m · n) time and O(m · n) extra space. 2^n first-row choices, each followed by one forced pass over the grid (each flip touches 5 cells).

Which pattern does Minimum Number of Flips to Convert Binary Matrix to Zero Matrix use?

It is a graphs problem that uses the bfs for shortest path pattern. Other problems with the same pattern: Shortest Path in Binary Matrix, Word Ladder, Bus Routes.

Is there a brute force solution for Minimum Number of Flips to Convert Binary Matrix to Zero Matrix?

Yes. Brute force (try every set of cells) takes O(2^(mn) · mn) time and O(mn) space. Because flips commute and flipping a cell twice cancels out, any solution is a subset of cells flipped once each.

Which edge cases should I test for Minimum Number of Flips to Convert Binary Matrix to Zero Matrix?

The matrix is already all zeros (answer 0); Grids where no sequence works (answer -1), such as 1 x 2 or some 2 x 3 patterns; A single cell; The all-ones 3 x 3 grid, which needs many flips.