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.
Breadth-First Search with Bitmask Encoding: In this approach, we use a BFS to explore all possible states of the matrix, representing each state as a bitmask. Each bit in the bitmask represents a cell in the matrix, allowing us to efficiently keep track of visited states. Starting from the initial matrix configuration, we flip each cell and its neighbors, transforming the state and pushing it into our BFS queue. By marking visited states, we avoid cycles and redundant operations. We continue this process until we either find a zero matrix or exhaust all possibilities, at which point we return -1.
Python BFS Explanation: We start by encoding the matrix into a single integer called a bitmask. Each bit in the integer represents a cell in the matrix. We use BFS to traverse all possible flips in the matrix, starting from the initial configuration. If a state reaches a zero matrix (bitmask == 0), we return the number of steps taken. We track visited states to avoid reprocessing states.
Complexity: Time Complexity: O(N * 2^(M*N)), where N is the number of cells, as we are exploring all possible states. Space Complexity: O(2^(M*N)) for the visited set and queue.
The problem can be tackled using a Breadth-First Search (BFS) approach, where we treat each matrix state as a node in a graph. The challenge is to explore all possible ways to make the minimum number of transformations from the initial matrix to a zero matrix. To efficiently manage and transition between states, we encode the matrix as a bitmask. Each state represents a particular configuration of the matrix.
Every time we flip a cell, it impacts the cell itself and its neighbors. For each state, we systematically toggle each cell and add the new resulting state to the BFS queue, marking states as visited to prevent redundant checks.
This Python solution uses a BFS strategy to examine states derived from flipping cells, leveraging bit manipulation to represent matrix configurations. 'mat_to_bits' encodes the matrix state to an integer, while 'bits_to_mat' decodes it back. The function 'flip' updates the bit representation by toggling the cell and its neighbors. The BFS explores all possible states, maintaining a queue and a set for visited states to prevent duplicate work. The method returns the number of flips needed or -1 if conversion isn't feasible.
Time Complexity: O(2^(m*n) * m * n). We consider all possible matrix states (2^(m*n)). Each state performs an O(m*n) flip operation.
Space Complexity: O(2^(m*n)). We need space for the queue and visited set, each holding up to 2^(m*n) states.
An alternative approach to solving the problem is through Depth-First Search (DFS) with Iterative Deepening. In this method, we explore the state space in a systematic and recursive manner, delving deeper into each potential flip configuration. We begin with a depth limit and increment gradually, attempting not to exceed this limit. The matrix state is represented at each node recursively, experimenting with each cell-flip combination.
The DFS pathway explores all configurations actively till terminal state clearance (zero matrix or true end-node) is discovered or edge constraints reach limits.
This Java implementation employs an iterative deepening DFS. We maintain a depth-bound search, recursing deeply till reaching the current depth limit. 'dfs()' explores flipping combinations, checking at each step whether a zero matrix configuration is achievable within constraints. 'matToBits()' and 'flip()' manage state representation, while checking reached states recursively using a visited set to prevent repetition.
Java
Time Complexity: Exponential in the number of matrix cells in the worst case, due to exhaustive state exploration.
Space Complexity: O(2^(m*n)) due to recursion depth and visited set overhead.
| Approach | Complexity |
|---|---|
| Breadth-First Search with Bitmask Encoding | Complexity: Time Complexity: O(N * 2^(M*N)), where N is the number of cells, as we are exploring all possible states. Space Complexity: O(2^(M*N)) for the visited set and queue. |
| Breadth-First Search (BFS) with State Encoding | Time Complexity: O(2^(m*n) * m * n). We consider all possible matrix states (2^(m*n)). Each state performs an O(m*n) flip operation. |
| Depth-First Search (DFS) with Iterative Deepening | Time Complexity: Exponential in the number of matrix cells in the worst case, due to exhaustive state exploration. |
| Default Approach | — |
| 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 |
Leetcode 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix • Algorithms for Big Bucks • 3,634 views views
Watch 9 more video solutions →Practice Minimum Number of Flips to Convert Binary Matrix to Zero Matrix with our built-in code editor and test cases.
Practice on FleetCode