#1284

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Compute the minimum flips to convert a binary matrix to zero by toggling cells and neighbors using array scanning plus hash lookup.

array hash table bit manipulation breadth first search matrix

Problem Statement

Given an m x n binary matrix mat where each cell is either 0 or 1, you can select a cell and flip it along with its four adjacent neighbors. Flipping changes a 0 to 1 or a 1 to 0, and neighbors share a single edge with the flipped cell.

Return the minimum number of flips required to convert mat into a zero matrix. If no sequence of flips achieves a zero matrix, return -1. Constraints: 1 <= m, n <= 3.

Examples

Example 1

Input: mat = [[0,0],[0,1]]

Output: 3

One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.

Example 2

Input: mat = [[0]]

Output: 0

Given matrix is a zero matrix. We do not need to change it.

Example 3

Input: mat = [[1,0,0],[1,0,0]]

Output: -1

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 Approach

Bitmask Representation and BFS

Represent the matrix as a single integer using bitmasking, where each bit corresponds to a cell. Perform BFS from the initial state, flipping each cell and its neighbors to generate new states. Use a hash set to track visited states and avoid revisiting identical configurations.

Generate Flip Combinations Efficiently

Since flipping the same cell twice cancels the effect, consider each cell as either flipped once or not flipped. Enumerate all possible flip combinations using BFS levels to count steps. Stop BFS when reaching a zero matrix state.

Optimize with Hash Lookup

Store visited bitmask states in a hash table to quickly detect duplicates and prune BFS branches. This prevents exponential revisiting of identical configurations and ensures correct minimum step count calculation.

Complexity Analysis

Metric	Value
Time	O(M \cdot N \cdot 2 ^ N)
Space	O(N)

Time complexity is O(M * N * 2^(M N)) due to exploring all flip combinations for M x N matrix. Space complexity is O(2^(M N)) for the hash table storing visited states.

What Interviewers Usually Probe

Exploring small matrices with exponential state space is expected; interviewer may hint at bitmask BFS.
Mentioning repeated flips canceling each other can guide toward combination enumeration rather than naive recursion.
Using hash sets to avoid revisiting states is crucial for correctness and efficiency.

Common Pitfalls or Variants

Common pitfalls

Flipping a cell twice is redundant, but forgetting this leads to overcounting steps.
Not representing matrix as a bitmask may cause inefficient state storage and slow BFS.
Neglecting to track visited states can cause infinite loops in BFS.

Follow-up variants

Allow larger matrices where optimized pruning is required beyond BFS.
Only allow flipping cells without affecting neighbors, changing the pattern to single-cell toggling.
Count flips required to convert to a specific target matrix rather than zero matrix.

FAQ

What is the core pattern in Minimum Number of Flips to Convert Binary Matrix to Zero Matrix?

The main pattern is array scanning plus hash lookup, combined with bit manipulation to track flips efficiently.

Why do repeated flips of the same cell not change the matrix?

Flipping the same cell twice cancels the effect, so only consider flipping each cell at most once in combinations.

Can this approach scale to larger matrices?

The BFS with bitmasking works efficiently for 1 <= m, n <= 3; larger matrices require pruning or alternative optimizations.

How does bitmasking help in this problem?

Bitmasking encodes the matrix state as an integer, allowing fast state generation, comparison, and hash table storage.

What if the matrix cannot be converted to zero?

BFS will explore all possible flip combinations, and if zero matrix is unreachable, the algorithm correctly returns -1.

terminal

Solution

Solution 1

#### Python3

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

class Solution:
    def minFlips(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        state = sum(1 << (i * n + j) for i in range(m) for j in range(n) if mat[i][j])
        q = deque([state])
        vis = {state}
        ans = 0
        dirs = [0, -1, 0, 1, 0, 0]
        while q:
            for _ in range(len(q)):
                state = q.popleft()
                if state == 0:
                    return ans
                for i in range(m):
                    for j in range(n):
                        nxt = state
                        for k in range(5):
                            x, y = i + dirs[k], j + dirs[k + 1]
                            if not 0 <= x < m or not 0 <= y < n:
                                continue
                            if nxt & (1 << (x * n + y)):
                                nxt -= 1 << (x * n + y)
                            else:
                                nxt |= 1 << (x * n + y)
                        if nxt not in vis:
                            vis.add(nxt)
                            q.append(nxt)
            ans += 1
        return -1

Continue Practicing

#959 regions cut by slashes #1267 count servers that communicate #1311 get watched videos by your friends