Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
HardPrompt
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 either0or1.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach considers every possible way to flip the cells. Since each of the m*n cells can either be flipped or not, there are 2^(m*n) total combinations of flips. The algorithm iterates through each of these combinations, applies the flips to a copy of the matrix, and checks if the result is a zero matrix. It keeps track of the minimum number of flips required to achieve this state.
Algorithm
- Initialize
minFlipsto a very large value. - Get the matrix dimensions
mandn. - Iterate through every possible combination of flips. A combination can be represented by a bitmask
flipMaskof sizem*n, ranging from0to2^(m*n) - 1. - For each
flipMask:- Create a temporary copy of the input matrix.
- Calculate the number of flips in the current combination (
popcountofflipMask). - Apply the flips indicated by the
flipMaskto the temporary matrix. For each set bitkinflipMask, flip the cell at(k/n, k%n)and its neighbors. - After applying all flips, check if the temporary matrix is a zero matrix.
- If it is, update
minFlips = min(minFlips, currentFlips).
- After checking all masks, if
minFlipsis still the large initial value, return -1. Otherwise, returnminFlips.
Walkthrough
The core idea is to perform an exhaustive search over the solution space. We can represent a set of flips using a bitmask of length m*n. If the k-th bit of the mask is set to 1, it signifies that we perform a flip operation on the k-th cell of the matrix (when viewed as a 1D array). The algorithm iterates through all possible masks from 0 to 2^(m*n) - 1.
For each mask, we start with a fresh copy of the original matrix. We then apply the flips corresponding to the set bits in the mask. A flip operation at (r, c) involves toggling the values of the cell itself and its four cardinal neighbors (up, down, left, right), if they exist. After applying all flips for a given mask, we check if the entire matrix has been converted to zeros. If it has, we compare the number of flips used (which is the number of set bits in the mask) with the minimum number of flips found so far and update it if the current number is smaller. After iterating through all 2^(m*n) possibilities, the minimum value recorded is the answer. If no combination results in a zero matrix, it's impossible, and we return -1.
class Solution { public int minFlips(int[][] mat) { int m = mat.length; int n = mat[0].length; int minFlips = Integer.MAX_VALUE; for (int i = 0; i < (1 << (m * n)); i++) { int[][] tempMat = new int[m][n]; for(int r = 0; r < m; r++) { tempMat[r] = mat[r].clone(); } int currentFlips = 0; for (int j = 0; j < m * n; j++) { if ((i >> j & 1) == 1) { // This flip is part of the current combination int r = j / n; int c = j % n; flip(tempMat, r, c); } } if (isZeroMatrix(tempMat)) { // The number of flips is the number of set bits in i minFlips = Math.min(minFlips, Integer.bitCount(i)); } } return minFlips == Integer.MAX_VALUE ? -1 : minFlips; } private void flip(int[][] mat, int r, int c) { int m = mat.length; int n = mat[0].length; int[] dr = {0, 0, 0, 1, -1}; int[] dc = {0, 1, -1, 0, 0}; for (int i = 0; i < 5; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) { mat[nr][nc] ^= 1; } } } private boolean isZeroMatrix(int[][] mat) { for (int[] row : mat) { for (int cell : row) { if (cell == 1) { return false; } } } return true; }}Complexity
Time
O(2^(m*n) * m * n) - We iterate through `2^(m*n)` masks. For each, we apply up to `m*n` flips and then check the `m*n` cells.
Space
O(m * n) - to store a temporary copy of the matrix for each combination.
Trade-offs
Pros
Simple to conceptualize and implement.
Uses minimal extra space, only for a copy of the matrix.
Cons
Very high time complexity, making it impractical for larger matrices.
It explores the entire search space of
2^(m*n)combinations, even if an optimal solution is found early on.
This problem can be viewed as finding the shortest path in a graph where each node is a possible matrix configuration and an edge connects two configurations if one can be reached from the other by a single flip. Breadth-First Search (BFS) is the ideal algorithm for finding the shortest path in an unweighted graph. We start at the initial matrix state and explore layer by layer, where each layer corresponds to one additional flip, guaranteeing that the first time we reach the all-zero matrix, it will be with the minimum number of flips.
Algorithm
- Represent the matrix state as a bitmask. The initial matrix is the starting state.
- Initialize a queue for BFS and add the starting state's bitmask.
- Use a
visitedset to store bitmasks of states already added to the queue to avoid cycles. - Start BFS with
steps = 0. - In each level of the BFS:
- Process all states currently in the queue.
- For each state (mask), generate all
m*npossible next states by simulating a flip at each cell(r, c). - A flip at
(r, c)toggles the bits corresponding to(r, c)and its valid neighbors. - If a next state is the target (mask = 0), return
steps + 1. - If a next state has not been visited, add it to the queue and the
visitedset.
- If the queue becomes empty and the target was not reached, return -1.
Walkthrough
To implement BFS, we first need an efficient way to represent and manage the states of the matrix. A bitmask of length m*n is perfect for this. We can convert the m x n matrix into an integer where the k-th bit represents the value of the k-th cell.
The BFS algorithm starts with a queue containing the bitmask of the initial matrix. We also use a set to keep track of visited states to prevent redundant computations. The search proceeds in levels. At each level, we dequeue all the states added in the previous level. For each state, we generate all possible next states by applying a flip at each of the m*n cells. If any of these next states is the target state (a mask of all zeros), we have found the shortest path and can return the current level number as the answer. If a generated state has not been visited before, we add it to the queue and the visited set. If the queue becomes empty before we find the target state, it means the zero matrix is unreachable.
import java.util.HashSet;import java.util.LinkedList;import java.util.Queue;import java.util.Set; class Solution { public int minFlips(int[][] mat) { int m = mat.length; int n = mat[0].length; int startMask = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (mat[i][j] == 1) { startMask |= (1 << (i * n + j)); } } } if (startMask == 0) return 0; Queue<Integer> queue = new LinkedList<>(); Set<Integer> visited = new HashSet<>(); queue.offer(startMask); visited.add(startMask); int steps = 0; int[] dr = {0, 0, 0, 1, -1}; int[] dc = {0, 1, -1, 0, 0}; while (!queue.isEmpty()) { steps++; int size = queue.size(); for (int i = 0; i < size; i++) { int currentMask = queue.poll(); for (int k = 0; k < m * n; k++) { int r = k / n; int c = k % n; int nextMask = currentMask; for (int move = 0; move < 5; move++) { int nr = r + dr[move]; int nc = c + dc[move]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) { nextMask ^= (1 << (nr * n + nc)); } } if (nextMask == 0) return steps; if (!visited.contains(nextMask)) { visited.add(nextMask); queue.offer(nextMask); } } } } return -1; }}Complexity
Time
O(m * n * 2^(m*n)) - There are `2^(m*n)` states, and for each, we generate `m*n` potential next states.
Space
O(2^(m*n)) - In the worst case, the queue and visited set can hold all possible matrix states.
Trade-offs
Pros
Guaranteed to find the minimum number of flips.
Can be faster than exhaustive search if the minimum number of flips is small, as it terminates upon finding the first solution.
Cons
High space complexity, as it may need to store all
2^(m*n)states in the worst case.Time complexity is asymptotically the same as exhaustive search and can be slow if the minimum number of flips is large.
This highly optimized approach is based on a key observation from similar grid-based puzzles like 'Lights Out'. The decision to flip cells in the first row determines the necessary flips for the rest of the matrix. Once we decide on the flips for row i, the state of row i is set. To make row i all zeros, we can only use flips from row i+1, as any other flips would disrupt the already-zeroed-out rows above. This dependency allows us to reduce the search space from 2^(m*n) to just 2^min(m,n).
Algorithm
- To optimize, ensure
nis the smaller dimension of the matrix (transpose ifm > n). - Initialize
minFlipsto a very large value. - Iterate through all
2^npossible flip combinations for the first row, using a mask from0to2^n - 1. - For each first-row
mask:- Create a temporary copy of the matrix.
- Count flips for the first row based on the
maskand apply them. - Iterate from the second row (
r = 1) to the last (r = m-1). For each cell(r-1, c)in the previous row:- If
tempMat[r-1][c]is 1, we must flip the cell(r, c)below it to zero it out. Perform this flip and increment the flip count.
- If
- After processing all rows, the top
m-1rows are guaranteed to be zero. - Check if the last row is also all zeros.
- If it is, update
minFlipswith the total count for this combination.
- Return
minFlipsif a solution was found, otherwise -1.
Walkthrough
Instead of trying every possible flip combination, we only need to decide on the flips for the first row. There are 2^n ways to do this. For each of these 2^n initial choices, the flips for all subsequent rows become deterministic.
Here's why: consider row i. To make it a row of zeros, we look at its current state. The state of a cell (i, j) is affected by flips at (i, j) and its neighbors. Crucially, to change the state of (i, j) without affecting rows 0 to i-1, our only option is to flip the cell (i+1, j) in the row below. Therefore, after we fix the flips for the first row, we can proceed row by row. For each row r from 1 to m-1, we look at the row above it, r-1. If a cell mat[r-1][c] is 1, we must flip mat[r][c] to turn mat[r-1][c] to 0. We apply this logic iteratively down the matrix.
After this process, the top m-1 rows will be all zeros. The solution is valid only if the last row also happens to become all zeros. We try all 2^n initial first-row flip patterns, calculate the total flips for each valid solution, and take the minimum.
class Solution { public int minFlips(int[][] mat) { int m = mat.length; int n = mat[0].length; int minFlips = Integer.MAX_VALUE; // Iterate through all 2^n possibilities for flipping the first row for (int i = 0; i < (1 << n); i++) { int[][] tempMat = new int[m][n]; for(int r = 0; r < m; r++) { tempMat[r] = mat[r].clone(); } int currentFlips = 0; // Step 1: Apply flips to the first row based on the mask 'i' for (int j = 0; j < n; j++) { if ((i >> j & 1) == 1) { flip(tempMat, 0, j); } } currentFlips = Integer.bitCount(i); // Step 2: For subsequent rows, flip based on the state of the previous row for (int r = 1; r < m; r++) { for (int c = 0; c < n; c++) { if (tempMat[r - 1][c] == 1) { currentFlips++; flip(tempMat, r, c); } } } // Step 3: Check if the last row is all zeros if (isLastRowZero(tempMat)) { minFlips = Math.min(minFlips, currentFlips); } } return minFlips == Integer.MAX_VALUE ? -1 : minFlips; } private void flip(int[][] mat, int r, int c) { int m = mat.length; int n = mat[0].length; int[] dr = {0, 0, 0, 1, -1}; int[] dc = {0, 1, -1, 0, 0}; for (int i = 0; i < 5; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nr < m && nc >= 0 && nc < n) { mat[nr][nc] ^= 1; } } } private boolean isLastRowZero(int[][] mat) { int m = mat.length; int n = mat[0].length; for (int j = 0; j < n; j++) { if (mat[m - 1][j] == 1) { return false; } } return true; }}Complexity
Time
O(m * n * 2^min(m,n)) - We iterate `2^n` times (or `2^m` if we optimize by transposing), and each iteration involves a pass over the matrix.
Space
O(m * n) - For storing a temporary copy of the matrix for each of the `2^n` trials.
Trade-offs
Pros
The most time-efficient approach due to a significantly reduced search space.
Maintains a low space complexity.
Cons
The logic is more complex and less intuitive than a direct search or BFS.
Solutions
Solution
class Solution {public int minFlips(int[][] mat) { int m = mat.length, n = mat[0].length; int state = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (mat[i][j] == 1) { state |= 1 << (i * n + j); } } } Deque<Integer> q = new ArrayDeque<>(); q.offer(state); Set<Integer> vis = new HashSet<>(); vis.add(state); int ans = 0; int[] dirs = {0, -1, 0, 1, 0, 0}; while (!q.isEmpty()) { for (int t = q.size(); t > 0; --t) { state = q.poll(); if (state == 0) { return ans; } for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int nxt = state; for (int k = 0; k < 5; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x < 0 || x >= m || y < 0 || y >= n) { continue; } if ((nxt & (1 << (x * n + y))) != 0) { nxt -= 1 << (x * n + y); } else { nxt |= 1 << (x * n + y); } } if (!vis.contains(nxt)) { vis.add(nxt); q.offer(nxt); } } } } ++ans; } return -1; }}class Solution {public: int minFlips(vector<vector<int>> &mat) { int m = mat.size(), n = mat[0].size(); int state = 0; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (mat[i][j]) state |= (1 << (i * n + j)); queue<int> q{{state}}; unordered_set<int> vis{{state}}; int ans = 0; vector<int> dirs = {0, -1, 0, 1, 0, 0}; while (!q.empty()) { for (int t = q.size(); t; --t) { state = q.front(); if (state == 0) return ans; q.pop(); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int nxt = state; for (int k = 0; k < 5; ++k) { int x = i + dirs[k], y = j + dirs[k + 1]; if (x < 0 || x >= m || y < 0 || y >= n) continue; if ((nxt & (1 << (x * n + y))) != 0) nxt -= 1 << (x * n + y); else nxt |= 1 << (x * n + y); } if (!vis.count(nxt)) { vis.insert(nxt); q.push(nxt); } } } } ++ans; } return -1; }};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 - 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.