Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Problem

Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbors of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighbors if they share one edge.

Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot.

A binary matrix is a matrix with all cells equal to 0 or 1 only.

A zero matrix is a matrix with all cells equal to 0.

Examples

Example 1

1
2
3
4
5
6



![](https://assets.leetcode.com/uploads/2019/11/28/matrix.png)

Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

Example 2

1
2
3


Input: mat = [[0]]
Output: 0
Explanation: Given matrix is a zero matrix. We do not need to change it.

Example 3

1
2
3


Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix cannot be a zero matrix.

Constraints

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

Solution

Method 1 – BFS with Bitmask State

Intuition

Represent the matrix as a bitmask integer, where each bit is a cell. BFS explores all possible flip sequences, and the minimum number of flips to reach the zero matrix is the answer.

Approach

Encode the matrix as a bitmask integer.
Use BFS to explore all possible states, flipping each cell and its neighbors.
For each state, try flipping every cell and update the bitmask accordingly.
Track visited states to avoid cycles.
Stop when the bitmask is zero (all cells are zero).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution {
public:
    int minFlips(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        int 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);
        queue<pair<int, int>> q;
        unordered_set<int> vis;
        q.push({start, 0});
        vis.insert(start);
        vector<pair<int,int>> dirs{{0,0},{0,1},{0,-1},{1,0},{-1,0}};
        while (!q.empty()) {
            auto [mask, steps] = q.front(); q.pop();
            if (mask == 0) return steps;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int next = mask;
                    for (auto& d : dirs) {
                        int ni = i + d.first, nj = j + d.second;
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n)
                            next ^= 1 << (ni * n + nj);
                    }
                    if (!vis.count(next)) {
                        vis.insert(next);
                        q.push({next, steps+1});
                    }
                }
            }
        }
        return -1;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


func minFlips(mat [][]int) int {
    m, n := len(mat), len(mat[0])
    start := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if mat[i][j] == 1 {
                start |= 1 << (i*n + j)
            }
        }
    }
    type state struct{ mask, steps int }
    vis := map[int]bool{start: true}
    q := []state{{start, 0}}
    dirs := [][2]int{{0,0},{0,1},{0,-1},{1,0},{-1,0}}
    for len(q) > 0 {
        s := q[0]; q = q[1:]
        if s.mask == 0 { return s.steps }
        for i := 0; i < m; i++ {
            for j := 0; j < n; j++ {
                next := s.mask
                for _, d := range dirs {
                    ni, nj := i+d[0], j+d[1]
                    if ni >= 0 && ni < m && nj >= 0 && nj < n {
                        next ^= 1 << (ni*n + nj)
                    }
                }
                if !vis[next] {
                    vis[next] = true
                    q = append(q, state{next, s.steps+1})
                }
            }
        }
    }
    return -1
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution {
    public int minFlips(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int 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);
        Queue<int[]> q = new LinkedList<>();
        Set<Integer> vis = new HashSet<>();
        q.offer(new int[]{start, 0});
        vis.add(start);
        int[][] dirs = {{0,0},{0,1},{0,-1},{1,0},{-1,0}};
        while (!q.isEmpty()) {
            int[] s = q.poll();
            int mask = s[0], steps = s[1];
            if (mask == 0) return steps;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int next = mask;
                    for (int[] d : dirs) {
                        int ni = i + d[0], nj = j + d[1];
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n)
                            next ^= 1 << (ni * n + nj);
                    }
                    if (!vis.contains(next)) {
                        vis.add(next);
                        q.offer(new int[]{next, steps+1});
                    }
                }
            }
        }
        return -1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


class Solution {
    fun minFlips(mat: Array<IntArray>): Int {
        val m = mat.size
        val n = mat[0].size
        var start = 0
        for (i in 0 until m)
            for (j in 0 until n)
                if (mat[i][j] == 1) start = start or (1 shl (i * n + j))
        val vis = mutableSetOf<Int>()
        val q = ArrayDeque<Pair<Int, Int>>()
        q.add(start to 0)
        vis.add(start)
        val dirs = arrayOf(intArrayOf(0,0), intArrayOf(0,1), intArrayOf(0,-1), intArrayOf(1,0), intArrayOf(-1,0))
        while (q.isNotEmpty()) {
            val (mask, steps) = q.removeFirst()
            if (mask == 0) return steps
            for (i in 0 until m) {
                for (j in 0 until n) {
                    var next = mask
                    for (d in dirs) {
                        val ni = i + d[0]; val nj = j + d[1]
                        if (ni in 0 until m && nj in 0 until n)
                            next = next xor (1 shl (ni * n + nj))
                    }
                    if (next !in vis) {
                        vis.add(next)
                        q.add(next to steps+1)
                    }
                }
            }
        }
        return -1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution:
    def minFlips(self, mat: list[list[int]]) -> int:
        from collections import deque
        m, n = len(mat), len(mat[0])
        start: int = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    start |= 1 << (i * n + j)
        vis = set()
        q = deque([(start, 0)])
        vis.add(start)
        dirs = [(0,0),(0,1),(0,-1),(1,0),(-1,0)]
        while q:
            mask, steps = q.popleft()
            if mask == 0:
                return steps
            for i in range(m):
                for j in range(n):
                    next = mask
                    for dx, dy in dirs:
                        ni, nj = i+dx, j+dy
                        if 0<=ni<m and 0<=nj<n:
                            next ^= 1 << (ni * n + nj)
                    if next not in vis:
                        vis.add(next)
                        q.append((next, steps+1))
        return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


use std::collections::{HashSet, VecDeque};
impl Solution {
    pub fn min_flips(mat: Vec<Vec<i32>>) -> i32 {
        let m = mat.len();
        let n = mat[0].len();
        let mut start = 0;
        for i in 0..m {
            for j in 0..n {
                if mat[i][j] == 1 {
                    start |= 1 << (i * n + j);
                }
            }
        }
        let mut vis = HashSet::new();
        let mut q = VecDeque::new();
        q.push_back((start, 0));
        vis.insert(start);
        let dirs = [(0,0),(0,1),(0,-1),(1,0),(-1,0)];
        while let Some((mask, steps)) = q.pop_front() {
            if mask == 0 { return steps; }
            for i in 0..m {
                for j in 0..n {
                    let mut next = mask;
                    for &(dx, dy) in &dirs {
                        let ni = i as i32 + dx;
                        let nj = j as i32 + dy;
                        if ni >= 0 && ni < m as i32 && nj >= 0 && nj < n as i32 {
                            next ^= 1 << (ni as usize * n + nj as usize);
                        }
                    }
                    if !vis.contains(&next) {
                        vis.insert(next);
                        q.push_back((next, steps+1));
                    }
                }
            }
        }
        -1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


class Solution {
    minFlips(mat: number[][]): number {
        const m = mat.length, n = mat[0].length;
        let start = 0;
        for (let i = 0; i < m; ++i)
            for (let j = 0; j < n; ++j)
                if (mat[i][j]) start |= 1 << (i * n + j);
        const vis = new Set<number>();
        const q: [number, number][] = [[start, 0]];
        vis.add(start);
        const dirs = [[0,0],[0,1],[0,-1],[1,0],[-1,0]];
        while (q.length) {
            const [mask, steps] = q.shift()!;
            if (mask === 0) return steps;
            for (let i = 0; i < m; ++i) {
                for (let j = 0; j < n; ++j) {
                    let next = mask;
                    for (const [dx, dy] of dirs) {
                        const ni = i + dx, nj = j + dy;
                        if (ni >= 0 && ni < m && nj >= 0 && nj < n)
                            next ^= 1 << (ni * n + nj);
                    }
                    if (!vis.has(next)) {
                        vis.add(next);
                        q.push([next, steps+1]);
                    }
                }
            }
        }
        return -1;
    }
}

Complexity

⏰ Time complexity: O(m * n * 2^(m*n)), as each state is visited at most once and there are up to 2^(m*n) states.
🧺 Space complexity: O(2^(m*n)), for the visited set and BFS queue.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – BFS with Bitmask State#

Intuition#

Approach#

Code#

Complexity#