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

Posted on Edited on In

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

Description

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:

1
2
3
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:

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

Output: 1

Explanation:

Flipping the highlighted cell makes all the columns palindromic.

Example 3:

1
2
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^5
  • 0 <= grid[i][j] <= 1

Hints/Notes

Solution

Language: C++

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