# Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Hash Table, Matrix
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb)
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/image0.png) 

**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.length`
* `n == mat[i].length`
* `1 <= m, n <= 3`
* `mat[i][j]` is either `0` or `1`.

# Approaches
## Exhaustive Search
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   Initialize `minFlips` to a very large value.
*   Get the matrix dimensions `m` and `n`.
*   Iterate through every possible combination of flips. A combination can be represented by a bitmask `flipMask` of size `m*n`, ranging from `0` to `2^(m*n) - 1`.
*   For each `flipMask`:
    *   Create a temporary copy of the input matrix.
    *   Calculate the number of flips in the current combination (`popcount` of `flipMask`).
    *   Apply the flips indicated by the `flipMask` to the temporary matrix. For each set bit `k` in `flipMask`, 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 `minFlips` is still the large initial value, return -1. Otherwise, return `minFlips`.

## Breadth-First Search on State Space
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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 `visited` set 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*n` possible 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 `visited` set.
*   If the queue becomes empty and the target was not reached, return -1.

## Optimized Search by Fixing First Row
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)`.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
*   To optimize, ensure `n` is the smaller dimension of the matrix (transpose if `m > n`).
*   Initialize `minFlips` to a very large value.
*   Iterate through all `2^n` possible flip combinations for the first row, using a mask from `0` to `2^n - 1`.
*   For each first-row `mask`:
    *   Create a temporary copy of the matrix.
    *   Count flips for the first row based on the `mask` and 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.
    *   After processing all rows, the top `m-1` rows are guaranteed to be zero.
    *   Check if the last row is also all zeros.
    *   If it is, update `minFlips` with the total count for this combination.
*   Return `minFlips` if a solution was found, otherwise -1.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```