Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

You are given an m x n binary matrix. In one step, you choose any cell and flip it along with all four of its neighbors (up, down, left, right). "Flip" means toggling 0 to 1 or 1 to 0. Return the minimum number of steps to make every cell in the matrix equal to 0, or -1 if it is impossible.

This is LeetCode 1284: Minimum Number of Flips to Convert Binary Matrix to Zero Matrix, and it is a textbook example of BFS on a bitmask state space. The trick is recognizing that the entire matrix can be compressed into a single integer, and each "flip" operation is just a few XOR operations on that integer.

Why this problem matters

This problem sits at the intersection of two patterns that show up frequently in interviews: bit manipulation and BFS on implicit state graphs. On its own, neither concept is especially hard. But combining them requires you to think about state representation and state transitions at the same time.

The matrix is small (at most 3x3), which means the entire state space fits in a bitmask of at most 9 bits. That gives you at most 2^9 = 512 possible states. BFS can explore all of them in microseconds. The real challenge is not performance. It is seeing that each matrix configuration is a node in a graph, each flip operation is an edge, and "minimum flips" is the shortest path from your starting state to state 0.

Once you internalize this bitmask-BFS pattern, you can apply it to any problem where a small set of toggleable elements defines a state. Lights-out puzzles, lock combinations, and board game configurations all follow the same template.

The approach: BFS on bitmask states

Here is the plan:

1. Encode the matrix as a bitmask. Read cells row by row and pack them into an integer. For a 2x2 matrix [[0,0],[0,1]], cell (1,1) is bit 3, so the bitmask is 0b0010 = 2.

2. Precompute flip masks. For each cell (r, c), build a bitmask that has a 1 at position (r, c) and at every valid neighbor. When you XOR the current state with this mask, you get the state after flipping that cell.

3. Run BFS. Start from the initial bitmask. At each step, try all m * n possible flips. Each flip produces a new state via XOR. If the new state is 0, return the current distance plus 1. Otherwise, add it to the queue if you have not visited it.

The target state is always 0 (all bits off). BFS guarantees the shortest path because every edge has the same weight (one flip).

from collections import deque

def min_flips(mat: list[list[int]]) -> int:
    m, n = len(mat), len(mat[0])

    start = 0
    for r in range(m):
        for c in range(n):
            if mat[r][c]:
                start |= 1 << (r * n + c)

    if start == 0:
        return 0

    flip_masks = []
    for r in range(m):
        for c in range(n):
            mask = 1 << (r * n + c)
            for dr, dc in [(0, 0), (1, 0), (-1, 0), (0, 1), (0, -1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n:
                    mask |= 1 << (nr * n + nc)
            flip_masks.append(mask)

    visited = {start}
    queue = deque([(start, 0)])

    while queue:
        state, dist = queue.popleft()

        for mask in flip_masks:
            new_state = state ^ mask

            if new_state == 0:
                return dist + 1

            if new_state not in visited:
                visited.add(new_state)
                queue.append((new_state, dist + 1))

    return -1

Step-by-step walkthrough

Let us trace through the example mat = [[0,0],[0,1]].

BFS finds the answer in 2 flips. The path goes from state 2 to state 12 (by flipping cell (0,1)), then from state 12 to state 0 (by flipping cell (0,1) again). Each BFS level represents one additional flip, and the visited set ensures we never process the same state twice.

Notice how the same cell can be flipped more than once along a path. That is fine. BFS does not care about which cells you flip, only about the resulting state. Two different sequences of flips that produce the same bitmask are the same node in the graph.

Complexity analysis

For a 3x3 matrix, m * n = 9, so there are at most 2^9 = 512 states. For each state, you try 9 possible flips. That gives 512 * 9 = 4608 operations total, which is effectively constant. The space is O(512) for the visited set and queue. This approach works perfectly for the constraint that m and n are at most 3.

The building blocks

This problem combines three core techniques:

Bitmask state encoding. Instead of storing a 2D array for each state, you pack the entire matrix into an integer. Bit i represents cell (i / n, i % n). This makes states hashable, comparable, and trivially copyable. The same encoding works for any problem with a small number of binary cells.

BFS on state graphs. You never build an explicit adjacency list. Instead, you generate neighbors on the fly by applying each flip mask. The BFS template is identical to what you would use for Open the Lock, Sliding Puzzle, or Word Ladder. Start from the initial state, expand level by level, return the depth when you hit the target.

XOR for toggling bits. The flip operation maps perfectly to XOR. state ^ flip_mask toggles exactly the bits corresponding to the flipped cell and its neighbors. XOR is self-inverse, meaning flipping the same cell twice returns you to the original state. This property is what makes the state graph well-defined.

Edge cases to watch for

• Already zero: If the input matrix is all zeros, return 0 immediately. The bitmask is 0 from the start.
• Impossible configurations: Not every starting state can reach 0. If BFS exhausts the queue without finding state 0, return -1. For example, on a 1x1 matrix [[1]], flipping the only cell gives [[0]], so the answer is 1. But some larger configurations have no solution.
• Single row or column: When m = 1 or n = 1, some cells have only 1 or 2 neighbors instead of 4. The flip mask precomputation handles this automatically by checking bounds.
• All ones: The worst case for BFS depth. For a 3x3 matrix of all ones (state = 511), BFS may need to explore many levels before finding a path to 0 (or determining that none exists).

From understanding to recall

You have seen how BFS on a bitmask state space solves this matrix flipping problem: encode the matrix as an integer, precompute flip masks with XOR, and search for the shortest path to zero. The logic makes sense when you read through it step by step. But during an interview, you need to produce the bitmask encoding, the flip mask construction, and the BFS loop without hesitation.

Spaced repetition bridges that gap. CodeBricks drills the bitmask-state-BFS building block and the XOR-toggle pattern independently. You write each piece from scratch at increasing intervals until the code flows automatically. When a matrix flipping or state-space search problem appears in your interview, you do not pause to figure out how to encode states or generate neighbors. You just write it.

Related posts

• Sliding Puzzle - BFS on an implicit state graph where board configurations are nodes and tile swaps are edges
• Open the Lock - BFS shortest path on lock combinations, another classic state-space search
• Shortest Path in Binary Matrix - BFS on a grid, showing how shortest-path search applies to matrix problems