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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

Output: 2

Explanation:

![](https://assets.leetcode.com/uploads/2024/07/07/screenshot-
from-2024-07-08-00-20-10.png)

Flipping the highlighted cells makes all the rows palindromic.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

Output: 1

Explanation:

![](https://assets.leetcode.com/uploads/2024/07/07/screenshot-
from-2024-07-08-00-31-23.png)

Flipping the highlighted cell makes all the columns palindromic.

Example 3

1
2
3
4
5
6
7
8


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

Output: 0

Explanation:

All rows are already palindromic.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m * n <= 2 * 10^5
  • 0 <= grid[i][j] <= 1

Solution

Method 1 – Two Pointers for Palindromic Rows and Columns

Intuition

To make all rows or all columns palindromic, for each row or column, we only need to flip cells that break the palindrome property. For each row, compare symmetric cells and count mismatches; similarly for columns. The minimum flips needed is the minimum of total flips for all rows and all columns.

Approach

  1. For each row, use two pointers to compare symmetric cells and count flips needed.
  2. For each column, use two pointers to compare symmetric cells and count flips needed.
  3. Return the minimum of total row flips and total column flips.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int minFlips(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int row_flips = 0, col_flips = 0;
        for (int i = 0; i < m; ++i) {
            for (int l = 0, r = n-1; l < r; ++l, --r) {
                if (grid[i][l] != grid[i][r]) row_flips++;
            }
        }
        for (int j = 0; j < n; ++j) {
            for (int t = 0, b = m-1; t < b; ++t, --b) {
                if (grid[t][j] != grid[b][j]) col_flips++;
            }
        }
        return min(row_flips, col_flips);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func minFlips(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    rowFlips, colFlips := 0, 0
    for i := 0; i < m; i++ {
        for l, r := 0, n-1; l < r; l, r = l+1, r-1 {
            if grid[i][l] != grid[i][r] {
                rowFlips++
            }
        }
    }
    for j := 0; j < n; j++ {
        for t, b := 0, m-1; t < b; t, b = t+1, b-1 {
            if grid[t][j] != grid[b][j] {
                colFlips++
            }
        }
    }
    if rowFlips < colFlips {
        return rowFlips
    }
    return colFlips
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int minFlips(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int rowFlips = 0, colFlips = 0;
        for (int i = 0; i < m; ++i)
            for (int l = 0, r = n-1; l < r; ++l, --r)
                if (grid[i][l] != grid[i][r]) rowFlips++;
        for (int j = 0; j < n; ++j)
            for (int t = 0, b = m-1; t < b; ++t, --b)
                if (grid[t][j] != grid[b][j]) colFlips++;
        return Math.min(rowFlips, colFlips);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun minFlips(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        var rowFlips = 0
        var colFlips = 0
        for (i in 0 until m)
            for (l in 0 until n/2)
                if (grid[i][l] != grid[i][n-1-l]) rowFlips++
        for (j in 0 until n)
            for (t in 0 until m/2)
                if (grid[t][j] != grid[m-1-t][j]) colFlips++
        return minOf(rowFlips, colFlips)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def minFlips(self, grid: list[list[int]]) -> int:
        m: int = len(grid)
        n: int = len(grid[0])
        row_flips: int = 0
        col_flips: int = 0
        for i in range(m):
            for l in range(n//2):
                if grid[i][l] != grid[i][n-1-l]:
                    row_flips += 1
        for j in range(n):
            for t in range(m//2):
                if grid[t][j] != grid[m-1-t][j]:
                    col_flips += 1
        return min(row_flips, col_flips)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn min_flips(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut row_flips = 0;
        let mut col_flips = 0;
        for i in 0..m {
            for l in 0..n/2 {
                if grid[i][l] != grid[i][n-1-l] {
                    row_flips += 1;
                }
            }
        }
        for j in 0..n {
            for t in 0..m/2 {
                if grid[t][j] != grid[m-1-t][j] {
                    col_flips += 1;
                }
            }
        }
        row_flips.min(col_flips)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    minFlips(grid: number[][]): number {
        const m = grid.length, n = grid[0].length;
        let rowFlips = 0, colFlips = 0;
        for (let i = 0; i < m; ++i)
            for (let l = 0; l < Math.floor(n/2); ++l)
                if (grid[i][l] !== grid[i][n-1-l]) rowFlips++;
        for (let j = 0; j < n; ++j)
            for (let t = 0; t < Math.floor(m/2); ++t)
                if (grid[t][j] !== grid[m-1-t][j]) colFlips++;
        return Math.min(rowFlips, colFlips);
    }
}

Complexity

  • ⏰ Time complexity: O(mn), as we check each cell at most once.
  • 🧺 Space complexity: O(1), only a few variables are used.