Watch 10 video solutions for Minimum Number of Flips to Convert Binary Matrix to Zero Matrix, a hard level problem involving Array, Hash Table, Bit Manipulation. This walkthrough by Algorithms for Big Bucks has 3,634 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
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:
Input: mat = [[0]] Output: 0 Explanation: 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 Explanation: Given matrix cannot be a zero matrix.
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 3mat[i][j] is either 0 or 1.Problem Overview: You are given an m x n binary matrix. Flipping a cell toggles that cell and its four neighbors (up, down, left, right). The goal is to reach an all-zero matrix using the minimum number of flips. If no sequence of flips produces a zero matrix, return -1.
Approach 1: Breadth-First Search with Bitmask Encoding (Time: O(2^(m*n)), Space: O(2^(m*n)))
The matrix state can be compressed into a single integer using bit manipulation. Each bit represents a cell. A flip operation toggles the corresponding bit and the bits for its neighbors. Starting from the initial state, run Breadth-First Search across all reachable states. BFS guarantees the first time you reach the zero mask is the minimum number of flips. Use a visited set to avoid revisiting states. This works well because the matrix size is small (at most 3x3), so the state space is bounded by 2^(m*n).
Approach 2: BFS with Matrix State Encoding (Time: O(2^(m*n) * m * n), Space: O(2^(m*n)))
Instead of compressing the grid into a bitmask, encode the matrix as a string or flattened array and store it in a queue for BFS. For every state, iterate through each cell and simulate a flip by toggling the cell and its neighbors inside the matrix. Each generated configuration becomes a new node in the search graph. A hash set tracks visited configurations. This approach is easier to reason about but slower due to repeated matrix copying and string construction.
Approach 3: DFS with Iterative Deepening (Time: O(b^d) worst case, Space: O(d))
Depth-First Search with iterative deepening tries all flip sequences up to a certain depth, then increases the depth limit. Each recursive step chooses a cell to flip and updates the matrix state. If the matrix becomes all zeros within the depth bound, the search stops. DFS uses less memory than BFS because it only keeps the current path in the call stack. However, it may revisit equivalent states and tends to be slower for this problem due to the branching factor of m * n.
Recommended for interviews: BFS with bitmask encoding is the expected solution. It shows you recognize that the matrix state space is small and can be modeled as a graph where each node is a configuration. Encoding the grid into an integer dramatically reduces memory usage and makes state transitions efficient. Interviewers typically expect BFS plus bit manipulation rather than raw matrix copying.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with Bitmask Encoding | O(2^(m*n)) | O(2^(m*n)) | Best overall approach when matrix size is small and states can be compressed into a bitmask |
| BFS with Matrix State Encoding | O(2^(m*n) * m * n) | O(2^(m*n)) | Useful when bit manipulation is avoided or when clarity is preferred over performance |
| DFS with Iterative Deepening | O(b^d) | O(d) | Memory-constrained scenarios or when exploring bounded search depth |