# Minimum Number of Flips to Make Binary Grid Palindromic I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-flips-to-make-binary-grid-palindromic-i)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-flips-to-make-binary-grid-palindromic-i
**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 **either** all rows **palindromic** or all columns **palindromic**.

**Example 1:**

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

**Output:** 2

**Explanation:**

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

Flipping the highlighted cells makes all the rows palindromic.

**Example 2:**

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

**Output:** 1

**Explanation:**

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

Flipping the highlighted cell makes all the columns palindromic.

**Example 3:**

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

**Output:** 0

**Explanation:**

All rows are already palindromic.

**Constraints:**

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

# Approaches
## Calculation using Temporary Arrays
This approach calculates the minimum flips required for rows and columns separately. To simplify the palindrome check for each row or column, it first copies the row or column data into a temporary 1D array. Then, it computes the flips needed for this temporary array. This process is repeated for all rows and then for all columns. The final answer is the minimum of the two calculated totals.
**Time:** O(m * n). For rows, we iterate `m` times. Inside the loop, copying `n` elements and then checking `n/2` pairs is `O(n)`. The total for rows is `O(m * n)`. Similarly, for columns, it's `O(n * m)`. The overall complexity is `O(m * n)`. · **Space:** O(max(m, n)). In each iteration, we create a temporary array of size `n` (for rows) or `m` (for columns). The space required is determined by the larger of these two dimensions.
**Pros:** The logic is very clear, separating the palindrome check into a reusable helper function.; Conceptually simple to understand and implement.
**Cons:** Uses extra space, which is unnecessary for this problem.; Copying data to temporary arrays adds computational overhead compared to direct access.
### Explanation
The core idea is to break down the problem into two independent parts: making all rows palindromic and making all columns palindromic.

To calculate the flips for rows, we iterate through each row of the grid. For each row, we copy its elements into a new temporary array. We then use a standard two-pointer technique on this array to count the number of mismatches between symmetric elements (`arr[k]` and `arr[len-1-k]`). The sum of these mismatches across all rows gives the total flips for the row-based case.

A similar procedure is followed for the columns. We iterate through each column, copy it to a temporary array, and calculate the flips needed to make it a palindrome.

Finally, the minimum of the total row flips and total column flips is returned. While straightforward, this method incurs additional space cost for the temporary arrays.

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

        // Case 1: Make all rows palindromic
        int rowFlips = 0;
        for (int i = 0; i < m; i++) {
            int[] tempRow = new int[n];
            for (int j = 0; j < n; j++) {
                tempRow[j] = grid[i][j];
            }
            rowFlips += countFlipsForPalindrome(tempRow);
        }

        // Case 2: Make all columns palindromic
        int colFlips = 0;
        for (int j = 0; j < n; j++) {
            int[] tempCol = new int[m];
            for (int i = 0; i < m; i++) {
                tempCol[i] = grid[i][j];
            }
            colFlips += countFlipsForPalindrome(tempCol);
        }

        return Math.min(rowFlips, colFlips);
    }

    private int countFlipsForPalindrome(int[] arr) {
        int flips = 0;
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            if (arr[left] != arr[right]) {
                flips++;
            }
            left++;
            right--;
        }
        return flips;
    }
}
```
### Algorithm
- Define a helper function `countFlipsForPalindrome(arr)` that takes a 1D array and returns the minimum flips to make it a palindrome using a two-pointer approach.
- Initialize `rowFlips = 0`.
- Iterate from `i = 0` to `m-1` (for each row):
  - Create a temporary array `tempRow` of size `n`.
  - Copy `grid[i]` to `tempRow`.
  - Add the result of `countFlipsForPalindrome(tempRow)` to `rowFlips`.
- Initialize `colFlips = 0`.
- Iterate from `j = 0` to `n-1` (for each column):
  - Create a temporary array `tempCol` of size `m`.
  - Copy column `j` of `grid` to `tempCol`.
  - Add the result of `countFlipsForPalindrome(tempCol)` to `colFlips`.
- Return `Math.min(rowFlips, colFlips)`.

## Direct In-Place Calculation
This is the optimal approach. It calculates the required flips for rows and columns without using any extra space for temporary data structures. It directly iterates through the grid and compares symmetric elements in-place, leading to an O(1) space complexity solution.
**Time:** O(m * n). The loop for rows runs `m * (n/2)` times. The loop for columns runs `n * (m/2)` times. The total time complexity is linear in the number of cells in the grid. · **Space:** O(1). This approach only uses a few variables to store the counts and loop indices, requiring constant extra space.
**Pros:** Optimal time and space complexity.; Highly efficient as it avoids data copying and works in-place.; The code is concise and directly implements the logic.
**Cons:** No significant cons; this is the standard and most efficient way to solve the problem.
### Explanation
This method also computes the flips for the row-palindromic case and the column-palindromic case separately and takes the minimum.

To calculate flips for making all rows palindromic, it iterates through each row `i`. For each row, it uses two pointers implicitly by iterating `j` from `0` to `n/2 - 1` and comparing `grid[i][j]` with `grid[i][n-1-j]`. If they differ, a flip is counted. This avoids creating a temporary array for the row.

A similar in-place logic is applied to calculate the flips for making all columns palindromic. For each column `j`, it iterates `i` from `0` to `m/2 - 1` and compares `grid[i][j]` with `grid[m-1-i][j]`, counting mismatches.

This approach achieves the same result as the previous one but with constant extra space, making it more efficient.

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

        // Case 1: Make all rows palindromic
        int rowFlips = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n / 2; j++) {
                if (grid[i][j] != grid[i][n - 1 - j]) {
                    rowFlips++;
                }
            }
        }

        // Case 2: Make all columns palindromic
        int colFlips = 0;
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m / 2; i++) {
                if (grid[i][j] != grid[m - 1 - i][j]) {
                    colFlips++;
                }
            }
        }

        return Math.min(rowFlips, colFlips);
    }
}
```
### Algorithm
- Initialize `rowFlips = 0`.
- Iterate through each row `i` from `0` to `m-1`.
- For each row, iterate with a column index `j` from `0` to `n/2 - 1`.
- Compare `grid[i][j]` with its symmetric element `grid[i][n-1-j]`. If they differ, increment `rowFlips`.
- Initialize `colFlips = 0`.
- Iterate through each column `j` from `0` to `n-1`.
- For each column, iterate with a row index `i` from `0` to `m/2 - 1`.
- Compare `grid[i][j]` with its symmetric element `grid[m-1-i][j]`. If they differ, increment `colFlips`.
- Return `Math.min(rowFlips, colFlips)`.

# Solutions
### Java

```java
class Solution {
public
  int minFlips(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int cnt1 = 0, cnt2 = 0;
    for (var row : grid) {
      for (int j = 0; j < n / 2; ++j) {
        if (row[j] != row[n - j - 1]) {
          ++cnt1;
        }
      }
    }
    for (int j = 0; j < n; ++j) {
      for (int i = 0; i < m / 2; ++i) {
        if (grid[i][j] != grid[m - i - 1][j]) {
          ++cnt2;
        }
      }
    }
    return Math.min(cnt1, cnt2);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minFlips(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    int cnt1 = 0, cnt2 = 0;
    for (const auto &row : grid) {
      for (int j = 0; j < n / 2; ++j) {
        if (row[j] != row[n - j - 1]) {
          ++cnt1;
        }
      }
    }
    for (int j = 0; j < n; ++j) {
      for (int i = 0; i < m / 2; ++i) {
        if (grid[i][j] != grid[m - i - 1][j]) {
          ++cnt2;
        }
      }
    }
    return min(cnt1, cnt2);
  }
};

```

### Python

```python
class Solution:
    def minFlips(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) cnt1 = cnt2 = 0 for row in grid: for j in range(n // 2): if row[j] != row[n - j - 1]: cnt1 += 1 for j in range(n): for i in range(m // 2): if grid[i][j] != grid[m - i - 1][j]: cnt2 += 1 return min(cnt1, cnt2)

```