LeetCode 3240 - Minimum Number of Flips to Make Binary Grid Palindromic II

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Matrix

Solution

Problem Understanding

We are given a binary matrix grid with m rows and n columns. Every cell contains either 0 or 1. We may flip any cell, meaning we can change 0 to 1 or 1 to 0.

The goal is to perform the minimum number of flips such that two conditions become true simultaneously:

Every row is palindromic.
Every column is palindromic.
The total number of 1s in the entire matrix is divisible by 4.

A row is palindromic if reading it from left to right gives the same sequence as reading it from right to left. Similarly, a column is palindromic if it reads the same from top to bottom and bottom to top.

The important observation is that making both rows and columns palindromic creates symmetry constraints between multiple cells. If a cell (i, j) must mirror another cell in its row and another in its column, eventually groups of cells become tied together and must all contain the same value.

For example, the following four positions are linked together:

(i, j)
(i, n - 1 - j)
(m - 1 - i, j)
(m - 1 - i, n - 1 - j)

All of these cells must end up equal in any valid final configuration.

The constraints are large:

1 <= m * n <= 2 * 10^5

This immediately rules out exponential or brute-force search over all possible flip combinations. We need a solution close to linear time.

Several edge cases are especially important:

A matrix with only one row.
A matrix with only one column.
Odd dimensions, where a middle row or middle column exists.
A single center cell when both m and n are odd.
Cases where the matrix is already palindromic but the number of 1s is not divisible by 4.

These cases require careful handling because some symmetry groups contain four cells, some contain two cells, and the center cell may stand alone.

Approaches

Brute Force Approach

A brute-force solution would try every possible combination of cell flips. For each possible final matrix, we would check whether:

every row is palindromic,
every column is palindromic,
the total number of 1s is divisible by 4.

Since each of the m * n cells can independently be either 0 or 1, there are:

$$2^{m \times n}$$

possible matrices.

For each matrix, verifying all conditions takes at least O(m * n) time.

This approach is completely infeasible for the given constraints because the grid may contain up to 200000 cells.

Key Insight

The critical insight is that row and column palindrome constraints force cells into symmetry groups.

For any position (i, j), the following cells must all become equal:

$$(i, j), (i, n-1-j), (m-1-i, j), (m-1-i, n-1-j)$$

This means we can process the matrix group by group instead of cell by cell.

Each group behaves independently with respect to palindrome requirements:

Either all cells in the group become 0
Or all cells in the group become 1

For a group of size four:

Cost to make all 0 = number of current 1s
Cost to make all 1 = number of current 0s

We choose the smaller cost.

Odd dimensions create special cases:

Middle row groups of size 2
Middle column groups of size 2
A center cell group of size 1

The divisibility-by-4 condition introduces an additional subtlety. Groups of size 4 always contribute either 0 or 4 ones, so they never affect divisibility modulo 4.

The only problematic groups are the size-2 groups and possibly the center cell.

By carefully tracking these groups, we can minimize flips while ensuring the total number of ones is divisible by 4.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(mn) m * n)	O(m * n)	Tries every possible matrix configuration
Optimal	O(m * n)	O(1)	Processes symmetry groups directly

Algorithm Walkthrough

Step 1: Process All Four-Cell Symmetry Groups

Iterate through the top-left quarter of the matrix.

For every position (i, j) in this region, collect the four symmetric cells:

(i, j)
(i, n-1-j)
(m-1-i, j)
(m-1-i, n-1-j)

Count how many of these cells are 1.

If the count is:

k ones,
then making the group all 0 costs k,
making the group all 1 costs 4-k.

Add:

$$\min(k, 4-k)$$

to the answer.

This guarantees the minimum cost for that group while preserving palindrome constraints.

Step 2: Handle the Middle Row, if `m` is Odd

If the number of rows is odd, there is a middle row that mirrors itself vertically.

Inside this row, pairs of symmetric columns must match:

(midRow, j)
(midRow, n-1-j)

Each pair behaves as a size-2 symmetry group.

There are two situations:

The pair already matches (00 or 11)
The pair differs (01 or 10)

If they differ, exactly one flip is required.

Track:

mismatches, the number of differing pairs
middleOnes, the number of ones contributed by matching 11 pairs

Step 3: Handle the Middle Column, if `n` is Odd

If the number of columns is odd, repeat the same logic for the middle column.

Each pair is:

(i, midCol)
(m-1-i, midCol)

Again:

differing pairs require one flip,
matching 11 pairs contribute two ones.

Step 4: Handle the Center Cell

If both m and n are odd, one center cell exists:

(m//2, n//2)

This cell forms a symmetry group of size 1.

To satisfy divisibility by 4, this center cell must ultimately become 0, because a single 1 changes the total modulo 4.

If the center cell is 1, add one flip.

Step 5: Resolve the Modulo Constraint for Size-2 Groups

Now we must ensure the total number of ones from all size-2 groups is divisible by 4.

Each matching 11 pair contributes 2 ones.

If there exists at least one mismatched pair, we can freely choose whether that pair becomes:

00
or 11

with the same cost of one flip.

This flexibility allows us to fix parity issues without extra cost.

If there are no mismatched pairs, then the number of ones contributed by size-2 groups is fixed.

If this value modulo 4 equals 2, we must flip one 11 pair into 00, costing two additional flips.

The final adjustment is therefore:

if mismatches > 0, add mismatches
else if middleOnes % 4 == 2, add 2

Why it Works

The algorithm works because palindrome constraints partition the matrix into independent symmetry groups. Every valid final matrix must assign the same value to all cells inside each group.

For size-4 groups, choosing the cheaper of all-zeros or all-ones is always optimal because these groups never affect divisibility modulo 4.

Only size-2 and size-1 groups affect the remainder modulo 4. The algorithm carefully tracks these groups and uses mismatched pairs as flexible adjustments whenever possible.

Since every group is processed optimally and independently, the total number of flips is globally minimal.

Python Solution

from typing import List

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

        flips = 0

        # Process groups of 4
        for r in range(rows // 2):
            for c in range(cols // 2):
                cells = [
                    grid[r][c],
                    grid[r][cols - 1 - c],
                    grid[rows - 1 - r][c],
                    grid[rows - 1 - r][cols - 1 - c]
                ]

                ones = sum(cells)
                flips += min(ones, 4 - ones)

        mismatches = 0
        middle_ones = 0

        # Middle row
        if rows % 2 == 1:
            middle_row = rows // 2

            for c in range(cols // 2):
                left = grid[middle_row][c]
                right = grid[middle_row][cols - 1 - c]

                if left != right:
                    mismatches += 1
                elif left == 1:
                    middle_ones += 2

        # Middle column
        if cols % 2 == 1:
            middle_col = cols // 2

            for r in range(rows // 2):
                top = grid[r][middle_col]
                bottom = grid[rows - 1 - r][middle_col]

                if top != bottom:
                    mismatches += 1
                elif top == 1:
                    middle_ones += 2

        # Center cell
        if rows % 2 == 1 and cols % 2 == 1:
            flips += grid[rows // 2][cols // 2]

        # Resolve modulo-4 condition
        if mismatches > 0:
            flips += mismatches
        else:
            if middle_ones % 4 == 2:
                flips += 2

        return flips

The implementation directly mirrors the algorithm.

The first nested loop processes all size-4 symmetry groups. For each group, we count the number of ones and choose the cheaper transformation.

Next, the code handles the middle row and middle column separately. These sections track two quantities:

mismatches, pairs requiring one mandatory flip,
middle_ones, the number of ones already locked into matching 11 pairs.

The center cell is processed independently because it forms a group of size one.

Finally, the modulo adjustment logic determines whether additional flips are needed to make the total number of ones divisible by four.

Go Solution

package main

func minFlips(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	flips := 0

	// Process groups of 4
	for r := 0; r < rows/2; r++ {
		for c := 0; c < cols/2; c++ {
			ones := 0

			ones += grid[r][c]
			ones += grid[r][cols-1-c]
			ones += grid[rows-1-r][c]
			ones += grid[rows-1-r][cols-1-c]

			if ones < 4-ones {
				flips += ones
			} else {
				flips += 4 - ones
			}
		}
	}

	mismatches := 0
	middleOnes := 0

	// Middle row
	if rows%2 == 1 {
		midRow := rows / 2

		for c := 0; c < cols/2; c++ {
			left := grid[midRow][c]
			right := grid[midRow][cols-1-c]

			if left != right {
				mismatches++
			} else if left == 1 {
				middleOnes += 2
			}
		}
	}

	// Middle column
	if cols%2 == 1 {
		midCol := cols / 2

		for r := 0; r < rows/2; r++ {
			top := grid[r][midCol]
			bottom := grid[rows-1-r][midCol]

			if top != bottom {
				mismatches++
			} else if top == 1 {
				middleOnes += 2
			}
		}
	}

	// Center cell
	if rows%2 == 1 && cols%2 == 1 {
		flips += grid[rows/2][cols/2]
	}

	// Resolve modulo-4 condition
	if mismatches > 0 {
		flips += mismatches
	} else {
		if middleOnes%4 == 2 {
			flips += 2
		}
	}

	return flips
}

The Go implementation follows the same structure as the Python version.

Go does not have Python's built-in sum, so the four-cell group count is accumulated manually.

All integers fit safely within Go's standard int type because the maximum number of cells is only 2 * 10^5.

Slices are used naturally for the matrix representation, and no additional memory allocation beyond a few counters is required.

Worked Examples

Example 1

Input:

[
  [1,0,0],
  [0,1,0],
  [0,0,1]
]

Step 1: Process Four-Cell Groups

Only one group exists:

Cells	Values	Ones	Cost
`(0,0) (0,2) (2,0) (2,2)`	`1 0 0 1`	2	2

Current flips = 2

Step 2: Middle Row

Middle row:

[0,1,0]

Pair:

Pair	Values	Result
`(1,0)` and `(1,2)`	`0 0`	matching

No mismatches.

Step 3: Middle Column

Middle column:

0 1 0

Pair:

Pair	Values	Result
`(0,1)` and `(2,1)`	`0 0`	matching

No mismatches.

Step 4: Center Cell

Center cell is 1.

Flip it.

Final flips:

2 + 1 = 3

Answer: 3

Example 2

Input:

[
  [0,1],
  [0,1],
  [0,0]
]

Step 1: Four-Cell Groups

No size-4 groups exist because cols // 2 = 1 but rows // 2 = 1, producing one group:

Cells	Values	Ones	Cost
`(0,0) (0,1) (2,0) (2,1)`	`0 1 0 0`	1	1

Flips = 1

Step 2: Middle Row

Middle row:

[0,1]

Pair:

Pair	Values	Result
`(1,0)` and `(1,1)`	`0 1`	mismatch

mismatches = 1

Step 3: Modulo Fix

Since mismatches exist, we can resolve parity without extra cost beyond the required flip.

Total flips:

1 + 1 = 2

Answer: 2

Example 3

Input:

[
  [1],
  [1]
]

Step 1: Four-Cell Groups

None.

Step 2: Middle Column

Only one pair:

Pair	Values	Result
`(0,0)` and `(1,0)`	`1 1`	matching

middle_ones = 2

Step 3: No Mismatches

Since:

middle_ones % 4 == 2

we must convert the pair into 00.

Cost = 2

Answer: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Every cell participates in at most one symmetry-group calculation
Space	O(1)	Only constant extra variables are used

The algorithm scans the matrix a constant number of times. No auxiliary arrays, hash maps, or recursion are required, so the extra memory usage remains constant regardless of input size.

Test Cases

sol = Solution()

assert sol.minFlips([[1,0,0],[0,1,0],[0,0,1]]) == 3
# Basic odd-sized example

assert sol.minFlips([[0,1],[0,1],[0,0]]) == 2
# Example with middle row mismatch

assert sol.minFlips([[1],[1]]) == 2
# Single column requiring modulo adjustment

assert sol.minFlips([[0]]) == 0
# Single zero cell already valid

assert sol.minFlips([[1]]) == 1
# Single one cell must become zero

assert sol.minFlips([[1,1],[1,1]]) == 0
# Already valid and divisible by 4

assert sol.minFlips([[1,0],[0,1]]) == 2
# Two diagonal ones

assert sol.minFlips([[0,0],[0,0]]) == 0
# All zeros

assert sol.minFlips([[1,1,1]]) == 1
# Single row with center cell

assert sol.minFlips([[1],[0],[1]]) == 2
# Single column with odd length

assert sol.minFlips([
    [1,0,1,0],
    [0,1,0,1],
    [1,0,1,0],
    [0,1,0,1]
]) == 8
# Larger even-sized matrix

assert sol.minFlips([
    [1,0,1],
    [1,1,1],
    [1,0,1]
]) == 1
# Only center cell violates divisibility

Test	Why
`[[1,0,0],[0,1,0],[0,0,1]]`	Validates odd dimensions and center handling
`[[0,1],[0,1],[0,0]]`	Validates middle row mismatch logic
`[[1],[1]]`	Validates modulo correction for size-2 groups
`[[0]]`	Smallest valid grid
`[[1]]`	Single center cell must flip
`[[1,1],[1,1]]`	Already optimal configuration
`[[1,0],[0,1]]`	Symmetry group conversion
`[[0,0],[0,0]]`	All-zero matrix
`[[1,1,1]]`	Single-row edge case
`[[1],[0],[1]]`	Single-column edge case
Larger 4x4 case	Stress test for multiple groups
Symmetric 3x3 case	Tests divisibility-only adjustment

Edge Cases

Single Cell Matrix

A 1 x 1 matrix is trivially palindromic because reversing a single element changes nothing. However, the divisibility condition still matters.

If the cell is 1, the total number of ones equals 1, which is not divisible by 4. The algorithm correctly flips the center cell to 0, requiring one operation.

Odd Dimensions with a Center Cell

When both dimensions are odd, the center cell belongs to no larger symmetry group. This is easy to overlook because all other cells appear in mirrored structures.

The implementation handles this explicitly with:

flips += grid[rows // 2][cols // 2]

This guarantees the center contributes 0 ones in the final configuration.

No Mismatched Size-2 Pairs

This is the trickiest case.

Suppose all middle-row and middle-column pairs already match, but the total number of ones contributed by these pairs equals 2 mod 4.

In this situation, parity cannot be fixed for free because there are no flexible mismatched pairs available. The algorithm correctly detects this and adds two extra flips to convert one 11 pair into 00.

Without this adjustment, many solutions incorrectly return a non-divisible total.

LeetCode 3240 - Minimum Number of Flips to Make Binary Grid Palindromic II

Solution

Problem Understanding

Approaches

Brute Force Approach

Key Insight

Approach Comparison

Algorithm Walkthrough

Step 1: Process All Four-Cell Symmetry Groups

Step 2: Handle the Middle Row, if m is Odd

Step 3: Handle the Middle Column, if n is Odd

Step 4: Handle the Center Cell

Step 5: Resolve the Modulo Constraint for Size-2 Groups

Why it Works

Python Solution

Go Solution

Worked Examples

Example 1

Step 1: Process Four-Cell Groups

Step 2: Middle Row

Step 3: Middle Column

Step 4: Center Cell

Example 2

Step 1: Four-Cell Groups

Step 2: Middle Row

Step 3: Modulo Fix

Example 3

Step 1: Four-Cell Groups

Step 2: Middle Column

Step 3: No Mismatches

Complexity Analysis

Test Cases

Edge Cases

Single Cell Matrix

Odd Dimensions with a Center Cell

No Mismatched Size-2 Pairs

Step 2: Handle the Middle Row, if `m` is Odd

Step 3: Handle the Middle Column, if `n` is Odd