Problem statement

You are given an m x n binary matrix mat. In one step you choose a cell and flip it together with its up-to-four neighbours (those sharing a side): every 0 among them becomes 1 and every 1 becomes 0.

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

Example 1

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: Flip (1,0), then (0,1), then (1,1).

Example 2

Input: mat = [[0]]
Output: 0
Explanation: It is already the zero matrix.

Example 3

Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: No sequence of flips clears this matrix.

Constraints

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 3
• mat[i][j] is 0 or 1

Hints for Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

1. Hint 1

   With at most 9 cells there are at most 2^9 = 512 possible matrices. Encode one as a bitmask.

2. Hint 2

   Each flip XORs the mask with a fixed pattern (the cell and its neighbours). Precompute the pattern for every cell.

3. Hint 3

   Run a BFS from the starting mask over these XOR moves; the distance at which mask 0 is first reached is the answer, and -1 if it never is.

How to solve Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

The matrix is tiny, so treat every matrix as a node of a graph with at most 512 nodes, joined by single flips, and find the shortest path to the zero matrix with breadth-first search.

Approach

1. Encode mat as a bitmask: bit i · n + j is mat[i][j].
2. For each cell build flip[k], the mask of that cell and its in-grid neighbours.
3. BFS from the start mask. From a mask x, the neighbours are x ^ flip[k] for every k.
4. Return the BFS distance of mask 0, or -1 if it is never reached.

Why it works

BFS on an unweighted graph returns the fewest edges to every reachable node; here an edge is one step. Because flips commute and flipping a cell twice undoes it, an optimal answer never flips a cell twice — at most 9 steps — but BFS does not need that fact to be correct.

Complexity

• Time — O(2^(m·n) · m · n)
• Space — O(2^(m·n))

Pitfalls

• Flipping includes the chosen cell itself, not only its neighbours.
• Neighbours outside the matrix are simply skipped — do not wrap around.
• Return 0 straight away when the matrix is already zero.

Reference solution

Python

from collections import deque
from typing import List

def minFlips(mat: List[List[int]]) -> int:
    m, n = len(mat), len(mat[0])
    start = 0
    for i in range(m):
        for j in range(n):
            if mat[i][j]:
                start |= 1 << (i * n + j)
    flips = []
    for i in range(m):
        for j in range(n):
            f = 0
            for r, c in ((i, j), (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                if 0 <= r < m and 0 <= c < n:
                    f |= 1 << (r * n + c)
            flips.append(f)
    dist = [-1] * (1 << (m * n))
    dist[start] = 0
    q = deque([start])
    while q:
        x = q.popleft()
        if x == 0:
            return dist[x]
        for f in flips:
            y = x ^ f
            if dist[y] == -1:
                dist[y] = dist[x] + 1
                q.append(y)
    return -1

Java

public static int minFlips(int[][] mat) {
    int m = mat.length, n = mat[0].length, start = 0;
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (mat[i][j] == 1) start |= 1 << (i * n + j);
    int[] dr = {0, 1, -1, 0, 0}, dc = {0, 0, 0, 1, -1};
    int[] flips = new int[m * n];
    for (int a = 0; a < m; a++) for (int b = 0; b < n; b++) {
        int f = 0;
        for (int k = 0; k < 5; k++) {
            int r = a + dr[k], c = b + dc[k];
            if (r >= 0 && c >= 0 && r < m && c < n) f |= 1 << (r * n + c);
        }
        flips[a * n + b] = f;
    }
    int[] dist = new int[1 << (m * n)];
    Arrays.fill(dist, -1);
    int[] q = new int[1 << (m * n)];
    int head = 0, tail = 0;
    dist[start] = 0;
    q[tail++] = start;
    while (head < tail) {
        int x = q[head++];
        if (x == 0) return dist[x];
        for (int f : flips) {
            int y = x ^ f;
            if (dist[y] == -1) { dist[y] = dist[x] + 1; q[tail++] = y; }
        }
    }
    return -1;
}

C++

int minFlips(vector<vector<int>>& mat) {
    int m = mat.size(), n = mat[0].size(), start = 0;
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (mat[i][j]) start |= 1 << (i * n + j);
    int dr[5] = {0, 1, -1, 0, 0}, dc[5] = {0, 0, 0, 1, -1};
    vector<int> flips;
    for (int a = 0; a < m; a++) for (int b = 0; b < n; b++) {
        int f = 0;
        for (int k = 0; k < 5; k++) {
            int r = a + dr[k], c = b + dc[k];
            if (r >= 0 && c >= 0 && r < m && c < n) f |= 1 << (r * n + c);
        }
        flips.push_back(f);
    }
    vector<int> dist(1 << (m * n), -1);
    queue<int> q;
    dist[start] = 0;
    q.push(start);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (x == 0) return dist[x];
        for (int f : flips) {
            int y = x ^ f;
            if (dist[y] == -1) { dist[y] = dist[x] + 1; q.push(y); }
        }
    }
    return -1;
}

JavaScript

var minFlips = function(mat) {
    var m = mat.length, n = mat[0].length, start = 0, flips = [];
    for (var i = 0; i < m; i++) for (var j = 0; j < n; j++) if (mat[i][j]) start |= 1 << (i * n + j);
    var dr = [0, 1, -1, 0, 0], dc = [0, 0, 0, 1, -1];
    for (var a = 0; a < m; a++) for (var b = 0; b < n; b++) {
        var f = 0;
        for (var k = 0; k < 5; k++) {
            var r = a + dr[k], c = b + dc[k];
            if (r >= 0 && c >= 0 && r < m && c < n) f |= 1 << (r * n + c);
        }
        flips.push(f);
    }
    var dist = new Array(1 << (m * n));
    for (var t = 0; t < dist.length; t++) dist[t] = -1;
    dist[start] = 0;
    var q = [start];
    for (var h = 0; h < q.length; h++) {
        var x = q[h];
        if (x === 0) return dist[x];
        for (var z = 0; z < flips.length; z++) {
            var y = x ^ flips[z];
            if (dist[y] === -1) { dist[y] = dist[x] + 1; q.push(y); }
        }
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard