#3239

Medium

auto_awesomeTwo-pointer scanning with invariant tracking

LeetCode Problem Workspace

Minimum Number of Flips to Make Binary Grid Palindromic I

Find the minimum flips to make a binary grid palindromic by scanning with two pointers and tracking symmetry efficiently.

array two pointers matrix

Problem Statement

You are given an m x n binary grid. Each row and column must be palindromic, meaning the sequence of values reads the same forwards and backwards. You can flip any cell from 0 to 1 or from 1 to 0.

Determine the minimum number of flips required to make all rows and columns palindromic. Focus on symmetric positions across rows and columns and ensure the overall grid satisfies the palindromic property with minimal operations.

Examples

Example 1

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

Output: 2

Flipping the highlighted cells makes all the rows palindromic.

Example 2

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

Output: 1

Flipping the highlighted cell makes all the columns palindromic.

Example 3

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

Output: 0

All rows are already palindromic.

Constraints

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

Solution Approach

Two-pointer symmetry check

Use two pointers starting from the beginning and end of each row and column. Compare symmetric elements and identify mismatches that require flipping. Count flips needed for each symmetric pair without redundant operations.

Invariant tracking

Maintain counters for groups of four symmetric cells (top-left, top-right, bottom-left, bottom-right). Decide minimal flips by ensuring all four cells match using the least changes. This invariant ensures no double counting or missing flips.

Aggregate minimal flips

Sum all minimal flips from each symmetric group across the grid. Return the total count. This guarantees the final grid is palindromic in both rows and columns with minimal flips.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m*n) because every cell is visited at most once via two-pointer comparisons. Space complexity is O(1) beyond the input grid, as only counters for symmetric groups are stored.

What Interviewers Usually Probe

Are you comparing symmetric cells only once per pair?
Can you track multiple cells together to minimize flips?
Does your approach handle grids with odd and even dimensions correctly?

Common Pitfalls or Variants

Common pitfalls

Flipping cells without checking all symmetric counterparts, leading to extra flips.
Miscounting flips in overlapping groups of four cells.
Ignoring odd-length rows or columns, which have a central element that should not be double-flipped.

Follow-up variants

Minimum flips for only row palindromes or only column palindromes.
Grids where only a subset of rows or columns need palindromic correction.
Larger grids requiring optimized grouping beyond 2x2 symmetric blocks.

FAQ

What pattern is used in Minimum Number of Flips to Make Binary Grid Palindromic I?

The two-pointer scanning with invariant tracking pattern is applied to detect symmetric mismatches and calculate minimal flips efficiently.

Can I flip a single cell multiple times?

No, each cell should be flipped at most once; the two-pointer invariant ensures minimal total flips.

Does the approach work for odd-sized grids?

Yes, central rows or columns are handled separately, ensuring the middle element is counted correctly if needed.

How do I minimize flips across overlapping symmetric groups?

Aggregate counts for groups of four symmetric cells and choose the minimal flips required to unify them.

What is the time complexity for large grids?

The solution runs in O(m*n) time since every cell is visited once during two-pointer symmetric comparisons.

terminal

Solution

Solution 1: Counting

We separately count the number of flips for rows and columns, denoted as $\textit{cnt1}$ and $\textit{cnt2}$, respectively. Finally, we take the minimum of the two.

1

2

3

4

5

6

7

8

9

10

11

12

13

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)

Continue Practicing

#3240 minimum number of flips to make binary grid palindromic ii #2503 maximum number of points from grid queries #3242 design neighbor sum service