# Minimum Number of Flips to Make Binary Grid Palindromic II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-flips-to-make-binary-grid-palindromic-ii)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-flips-to-make-binary-grid-palindromic-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, Matrix
---
## Problem
You are given an `m x n` binary matrix `grid`.

A row or column is considered **palindromic** if its values read the same forward and backward.

You can **flip** any number of cells in `grid` from `0` to `1`, or from `1` to `0`.

Return the **minimum** number of cells that need to be flipped to make **all** rows and columns **palindromic**, and the total number of `1`'s in `grid` **divisible** by `4`.

**Example 1:**

**Input:** grid = \[\[1,0,0\],\[0,1,0\],\[0,0,1\]\]

**Output:** 3

**Explanation:**

![](https://assets.glich.co/dsa/minimum-number-of-flips-to-make-binary-grid-palindromic-ii/image0.png)

**Example 2:**

**Input:** grid = \[\[0,1\],\[0,1\],\[0,0\]\]

**Output:** 2

**Explanation:**

![](https://assets.glich.co/dsa/minimum-number-of-flips-to-make-binary-grid-palindromic-ii/image1.png)

**Example 3:**

**Input:** grid = \[\[1\],\[1\]\]

**Output:** 2

**Explanation:**

![](https://assets.glich.co/dsa/minimum-number-of-flips-to-make-binary-grid-palindromic-ii/image2.png)

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m * n <= 2 * 105`
* `0 <= grid[i][j] <= 1`

# Approaches
## Naive Dynamic Programming
This approach uses dynamic programming to solve the problem by keeping track of the exact number of ones accumulated. While it correctly models the problem, its state space is very large, making it inefficient for the given constraints.
**Time:** O(G * S), where G is the number of symmetric groups (at most m*n) and S is the maximum number of ones (m*n). This leads to a complexity of O((m*n)^2). · **Space:** O(m*n) to store the DP table. The number of groups is also proportional to m*n, but they can be processed on the fly.
**Pros:** It is a direct and conceptually straightforward application of dynamic programming.; It correctly solves the problem for smaller grid sizes.
**Cons:** The time complexity of O((m*n)^2) is too high for the given constraints and will result in a Time Limit Exceeded error.; The space complexity of O(m*n) can be very large, potentially causing memory issues for the largest grids.
### Explanation
The core idea is to break down the problem into smaller, independent subproblems. The palindromic constraints force certain cells to be equal. We can group these cells together. For each group, we have two choices: make all cells 0 or make all cells 1. This problem can be framed as a variation of the knapsack problem.

We define a DP state `dp[j]` as the minimum flips to achieve exactly `j` ones. We iterate through each symmetric group and update the DP table based on the two choices for that group.

For a group of size `k` with costs `cost0` and `cost1`:
- To make it all 0s, we add `cost0` flips and 0 ones.
- To make it all 1s, we add `cost1` flips and `k` ones.

We build up the `dp` table group by group. After considering all groups, we look for the minimum flips among all states `dp[j]` where `j` is a multiple of 4.

```java
// This is a conceptual implementation and will likely time out.
class Solution {
    public int minFlips(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        List<int[]> groups = new ArrayList<>();
        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j]) continue;

                List<int[]> cells = new ArrayList<>();
                cells.add(new int[]{i, j});
                visited[i][j] = true;

                int r1 = i, c1 = n - 1 - j;
                if (!visited[r1][c1]) { cells.add(new int[]{r1, c1}); visited[r1][c1] = true; }
                int r2 = m - 1 - i, c2 = j;
                if (!visited[r2][c2]) { cells.add(new int[]{r2, c2}); visited[r2][c2] = true; }
                int r3 = m - 1 - i, c3 = n - 1 - j;
                if (!visited[r3][c3]) { cells.add(new int[]{r3, c3}); visited[r3][c3] = true; }

                int ones = 0;
                for (int[] cell : cells) {
                    if (grid[cell[0]][cell[1]] == 1) {
                        ones++;
                    }
                }
                int size = cells.size();
                int zeros = size - ones;
                groups.add(new int[]{size, ones, zeros}); // {k, cost0, cost1}
            }
        }

        int[] dp = new int[m * n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;

        for (int[] group : groups) {
            int k = group[0];
            int cost0 = group[1];
            int cost1 = group[2];
            int[] newDp = new int[m * n + 1];
            Arrays.fill(newDp, Integer.MAX_VALUE);

            for (int j = 0; j <= m * n; j++) {
                if (dp[j] != Integer.MAX_VALUE) {
                    // Option 1: Make group all 0s
                    newDp[j] = Math.min(newDp[j], dp[j] + cost0);
                    // Option 2: Make group all 1s
                    if (j + k <= m * n) {
                        newDp[j + k] = Math.min(newDp[j + k], dp[j] + cost1);
                    }
                }
            }
            dp = newDp;
        }

        int minFlips = Integer.MAX_VALUE;
        for (int j = 0; j <= m * n; j += 4) {
            minFlips = Math.min(minFlips, dp[j]);
        }

        return minFlips;
    }
}
```
### Algorithm
*   **Symmetric Group Decomposition:**
    1.  The first step is to realize that for the grid to be palindromic across all rows and columns, certain cells must have the same value. These cells form symmetric groups.
    2.  For any cell `(i, j)`, the cells `(i, n-1-j)`, `(m-1-i, j)`, and `(m-1-i, n-1-j)` must all have the same value. These four cells form a symmetric group of size 4.
    3.  If a row or column is in the middle (i.e., `m` or `n` is odd), the groups might be of size 2 or 1.
    4.  Iterate through the top-left quadrant of the grid to identify all unique symmetric groups and their original values.
*   **Cost Calculation:**
    1.  For each group, calculate the cost to make all its cells 0 (`cost0`, which is the number of 1s in the group) and the cost to make all its cells 1 (`cost1`, which is the number of 0s in the group).
*   **Dynamic Programming:**
    1.  Define a DP state `dp[i][j]` representing the minimum number of flips required using the first `i` groups to achieve a total of exactly `j` ones in the final grid.
    2.  The DP table size will be `(number of groups + 1) x (m*n + 1)`.
    3.  Initialize `dp[0][0] = 0` and all other entries to infinity.
    4.  The transition for group `i` (with size `k_i`, costs `cost0_i`, `cost1_i`) is:
        `dp[i][j] = min(dp[i-1][j] + cost0_i, dp[i-1][j - k_i] + cost1_i)`
    5.  This can be space-optimized to use a 1D DP array `dp[j]` of size `m*n + 1`.
*   **Final Result:**
    1.  After iterating through all groups, the DP table `dp[j]` will hold the minimum flips to get `j` ones.
    2.  The final answer is the minimum value among `dp[j]` for all `j` that are divisible by 4.

## Optimized Dynamic Programming with Modulo Arithmetic
This approach significantly optimizes the dynamic programming solution by reducing the state space. Instead of tracking the exact count of ones, we only track its remainder when divided by 4. This is sufficient because the problem only requires the total number of ones to be divisible by 4. This optimization reduces the time and space complexity to be linear in the size of the grid, making it highly efficient and capable of passing within the given constraints.
**Time:** O(m*n). We iterate through each cell of the grid once to form and process the symmetric groups. The DP update for each group takes constant time (O(4)). · **Space:** O(1), as the DP table size is constant (4), and the visited grid can be avoided by iterating smartly over the top-left quadrant.
**Pros:** Extremely efficient, with time complexity linear in the number of cells.; Optimal space complexity, using only a constant amount of extra space for the DP table.; It is the standard and best way to solve this type of knapsack-like problem with modular constraints.
**Cons:** The logic involving modulo arithmetic can be slightly more complex to grasp initially compared to the naive approach.
### Explanation
We start by identifying the same symmetric groups of cells as in the naive approach. For each group, we have two choices: make all its cells 0 or all 1. This choice affects the total flip count and the total number of ones.

The crucial observation is that the final condition on the number of ones, `total_ones % 4 == 0`, only depends on the sum of ones from each group modulo 4. This allows us to define a much smaller DP state: `dp[rem]`, the minimum flips needed to get a total number of ones congruent to `rem` (where `rem` is 0, 1, 2, or 3).

The DP table is an array of size 4. We process each symmetric group one by one, updating the DP table at each step. For a group of size `k`, if we choose to make it all 1s, the remainder of total ones will change from `rem` to `(rem + k) % 4`. If we make it all 0s, the remainder stays `rem`. We always choose the option that minimizes the flips for each possible resulting remainder.

After considering all groups, `dp[0]` will contain the minimum flips to satisfy all conditions.

```java
class Solution {
    public int minFlips(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        long[] dp = new long[4];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;

        boolean[][] visited = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j]) {
                    continue;
                }

                List<Integer> values = new ArrayList<>();
                int[] p1 = {i, j};
                int[] p2 = {i, n - 1 - j};
                int[] p3 = {m - 1 - i, j};
                int[] p4 = {m - 1 - i, n - 1 - j};

                if (!visited[p1[0]][p1[1]]) {
                    values.add(grid[p1[0]][p1[1]]);
                    visited[p1[0]][p1[1]] = true;
                }
                if (!visited[p2[0]][p2[1]]) {
                    values.add(grid[p2[0]][p2[1]]);
                    visited[p2[0]][p2[1]] = true;
                }
                if (!visited[p3[0]][p3[1]]) {
                    values.add(grid[p3[0]][p3[1]]);
                    visited[p3[0]][p3[1]] = true;
                }
                if (!visited[p4[0]][p4[1]]) {
                    values.add(grid[p4[0]][p4[1]]);
                    visited[p4[0]][p4[1]] = true;
                }

                int k = values.size();
                int ones = 0;
                for (int val : values) {
                    if (val == 1) {
                        ones++;
                    }
                }
                int zeros = k - ones;
                int cost0 = ones; // Flips to make all 0s
                int cost1 = zeros; // Flips to make all 1s

                dp = updateDp(dp, k, cost0, cost1);
            }
        }

        return (int) dp[0];
    }

    private long[] updateDp(long[] dp, int k, int cost0, int cost1) {
        long[] newDp = new long[4];
        Arrays.fill(newDp, Long.MAX_VALUE);
        for (int rem = 0; rem < 4; rem++) {
            if (dp[rem] != Long.MAX_VALUE) {
                // Choice 1: Make group all 0s
                int newRem0 = rem;
                long newFlips0 = dp[rem] + cost0;
                newDp[newRem0] = Math.min(newDp[newRem0], newFlips0);

                // Choice 2: Make group all 1s
                int newRem1 = (rem + k) % 4;
                long newFlips1 = dp[rem] + cost1;
                newDp[newRem1] = Math.min(newDp[newRem1], newFlips1);
            }
        }
        return newDp;
    }
}
```
### Algorithm
*   **Symmetric Group Decomposition:**
    1.  As in the previous approach, decompose the grid into symmetric groups of size `k` (which can be 1, 2, or 4). This is done by iterating through the top-left quadrant of the grid.
*   **Cost Calculation:**
    1.  For each group, calculate `cost0` (flips to make all 0s) and `cost1` (flips to make all 1s).
*   **Optimized Dynamic Programming:**
    1.  The key insight is that we only care about the total number of ones modulo 4. So, the DP state can be reduced.
    2.  Define `dp[rem]` as the minimum flips to achieve a total number of ones congruent to `rem` modulo 4.
    3.  The DP array `dp` will have a constant size of 4.
    4.  Initialize `dp[0] = 0` and `dp[1]`, `dp[2]`, `dp[3]` to infinity.
    5.  Iterate through each symmetric group (`k`, `cost0`, `cost1`).
    6.  In each iteration, compute a `new_dp` array based on the current `dp` array and the two choices for the current group:
        -   Choice 1 (make all 0s): Adds `cost0` to flips, number of ones' remainder does not change.
        -   Choice 2 (make all 1s): Adds `cost1` to flips, number of ones' remainder changes by `k % 4`.
    7.  Update `new_dp[rem]` and `new_dp[(rem + k) % 4]` for each `rem` from 0 to 3.
    8.  After processing the group, replace `dp` with `new_dp`.
*   **Final Result:**
    1.  After iterating through all groups, the value `dp[0]` will hold the minimum flips to make the total number of ones divisible by 4.

# Solutions
### Java

```java
class Solution {
public
  int minFlips(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int ans = 0;
    for (int i = 0; i < m / 2; ++i) {
      for (int j = 0; j < n / 2; ++j) {
        int x = m - i - 1, y = n - j - 1;
        int cnt1 = grid[i][j] + grid[x][j] + grid[i][y] + grid[x][y];
        ans += Math.min(cnt1, 4 - cnt1);
      }
    }
    if (m % 2 == 1 && n % 2 == 1) {
      ans += grid[m / 2][n / 2];
    }
    int diff = 0, cnt1 = 0;
    if (m % 2 == 1) {
      for (int j = 0; j < n / 2; ++j) {
        if (grid[m / 2][j] == grid[m / 2][n - j - 1]) {
          cnt1 += grid[m / 2][j] * 2;
        } else {
          diff += 1;
        }
      }
    }
    if (n % 2 == 1) {
      for (int i = 0; i < m / 2; ++i) {
        if (grid[i][n / 2] == grid[m - i - 1][n / 2]) {
          cnt1 += grid[i][n / 2] * 2;
        } else {
          diff += 1;
        }
      }
    }
    ans += cnt1 % 4 == 0 || diff > 0 ? diff : 2;
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minFlips(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int ans = 0;
    for (int i = 0; i < m / 2; ++i) {
      for (int j = 0; j < n / 2; ++j) {
        int x = m - i - 1, y = n - j - 1;
        int cnt1 = grid[i][j] + grid[x][j] + grid[i][y] + grid[x][y];
        ans += min(cnt1, 4 - cnt1);
      }
    }
    if (m % 2 == 1 && n % 2 == 1) {
      ans += grid[m / 2][n / 2];
    }
    int diff = 0, cnt1 = 0;
    if (m % 2 == 1) {
      for (int j = 0; j < n / 2; ++j) {
        if (grid[m / 2][j] == grid[m / 2][n - j - 1]) {
          cnt1 += grid[m / 2][j] * 2;
        } else {
          diff += 1;
        }
      }
    }
    if (n % 2 == 1) {
      for (int i = 0; i < m / 2; ++i) {
        if (grid[i][n / 2] == grid[m - i - 1][n / 2]) {
          cnt1 += grid[i][n / 2] * 2;
        } else {
          diff += 1;
        }
      }
    }
    ans += cnt1 % 4 == 0 || diff > 0 ? diff : 2;
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minFlips(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) ans = 0 for i in range(m // 2): for j in range(n // 2): x, y = m - i - 1, n - j - 1 cnt1 = grid[i][j] + grid[x][j] + grid[i][y] + grid[x][y] ans += min(cnt1, 4 - cnt1) if m % 2 and n % 2: ans += grid[m // 2][n // 2] diff = cnt1 = 0 if m % 2: for j in range(n // 2): if grid[m // 2][j] == grid[m // 2][n - j - 1]: cnt1 += grid[m // 2][j] * 2 else: diff += 1 if n % 2: for i in range(m // 2): if grid[i][n // 2] == grid[m - i - 1][n // 2]: cnt1 += grid[i][n // 2] * 2 else: diff += 1 ans += diff if cnt1 % 4 == 0 or diff else 2 return ans

```