3239. Minimum Number of Flips to Make Binary Grid Palindromic I

#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.

https://leetcode.cn/problems/minimum-number-of-flips-to-make-binary-grid-palindromic-i/

Example 1:

Input: grid = [[1,0,0],[0,0,0],[0,0,1]]
Output: 2
Explanation:

Flipping the highlighted cells makes all the rows palindromic.

Example 2:

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

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 * 10⁵
• 0 <= grid[i][j] <= 1

#Test Cases

class Solution:
    def minFlips(self, grid: List[List[int]]) -> int:

import pytest

from solution import Solution


@pytest.mark.parametrize('grid, expected', [
    ([[1,0,0],[0,0,0],[0,0,1]], 2),
    ([[0,1],[0,1],[0,0]], 1),
    ([[1],[0]], 0),
])
class Test:
    def test_solution(self, grid, expected):
        sol = Solution()
        assert sol.minFlips(grid) == expected

#Thoughts

对于一行，从两头往中间逐个比对，不一致的格子对数，就是需要翻转的数量（一对两个格子中翻转任意一个）。

行与行彼此独立，各行需要翻转的数量累加起来就是最终所有行都是回文所需的翻转总数。

同理求出所有列所需要的翻转总数。二者取最小。

时间复杂度 O(m * n)，空间复杂度 O(1)。

#Code

from typing import List


class Solution:
    def minFlips(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        flip_count_row = 0
        for row in grid:
            for j in range(n >> 1):
                if row[j] != row[-j - 1]:
                    flip_count_row += 1

        flip_count_col = 0
        for j in range(n):
            for i in range(m >> 1):
                if grid[i][j] != grid[-i - 1][j]:
                    flip_count_col += 1

        return min(flip_count_row, flip_count_col)