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

Solution

LeetCode 3239 - Minimum Number of Flips to Make Binary Grid Palindromic I

Problem Understanding

You are given a binary matrix grid with m rows and n columns. Every cell contains either 0 or 1.

A row is considered 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 reading it from top to bottom gives the same sequence as reading it from bottom to top.

You are allowed to flip any cell, meaning:

0 can become 1
1 can become 0

The goal is to compute the minimum number of flips needed so that:

either every row becomes palindromic,
or every column becomes palindromic.

You do not need both conditions simultaneously. You are allowed to choose whichever option requires fewer flips.

The input size constraint is important:

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

This tells us the grid can be very large in one dimension. For example:

1 x 200000
200000 x 1
447 x 447

Because the total number of cells can reach 200000, we need a solution that is close to linear in the number of cells. Any exponential or quadratic-over-cells solution would be too slow.

There are several important observations and edge cases:

A single-element row or column is always palindromic.
If n == 1, all rows are automatically palindromic.
If m == 1, all columns are automatically palindromic.
We only care about mirrored positions.
For a row, positions j and n - 1 - j must match.
For a column, positions i and m - 1 - i must match.

The problem guarantees that every cell is binary, so every mismatch can always be fixed with exactly one flip.

Approaches

Brute Force Approach

A naive idea would be to try every possible combination of flips and check whether all rows or all columns become palindromic.

For a grid with m * n cells, each cell has two states:

unchanged
flipped

That leads to 2^(m*n) possible configurations.

For every configuration, we would need to:

Apply flips.
Check all rows.
Check all columns.
Count flips.

This guarantees correctness because every possible transformed grid is examined. However, it is completely infeasible.

If the grid has even 30 cells, the number of configurations becomes enormous.

Key Insight

A palindrome only cares about mirrored pairs.

For rows:

grid[i][j]
grid[i][n - 1 - j]

must match.

If they already match:

no flip is needed.

If they differ:

exactly one flip is needed.

The same logic applies independently for columns.

Most importantly:

Row palindromicity depends only on row mirror pairs.
Column palindromicity depends only on column mirror pairs.

This means we can independently count:

flips needed to make all rows palindromic
flips needed to make all columns palindromic

Then return the smaller value.

This avoids any complicated state search.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(mn) m * n)	O(m * n)	Tries every possible flip configuration
Optimal	O(m * n)	O(1)	Counts mismatched mirrored pairs directly

Algorithm Walkthrough

Step 1: Compute flips needed for rows

For every row i, we compare mirrored positions:

grid[i][j]
grid[i][n - 1 - j]

We only need to iterate through half the row because every pair is checked once.

If the two values differ:

one flip is required.

We accumulate all such mismatches into row_flips.

Step 2: Compute flips needed for columns

For every column j, we compare mirrored positions:

grid[i][j]
grid[m - 1 - i][j]

Again, we only iterate through half the column.

If the values differ:

one flip is required.

We accumulate these mismatches into col_flips.

Step 3: Return the minimum

The problem asks for the minimum flips needed to make:

all rows palindromic, or
all columns palindromic.

Therefore, the answer is:

min(row_flips, col_flips)

Why it works

A palindrome constraint only requires mirrored positions to be equal.

For every mismatched mirrored pair:

at least one flip is necessary,
and exactly one flip is sufficient.

Since every pair is independent, counting mismatches directly gives the minimum flips needed.

The row calculation and column calculation are also independent because the problem allows satisfying either condition, not both simultaneously.

Python Solution

from typing import List

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

        row_flips = 0

        # Count flips needed to make all rows palindromic
        for r in range(rows):
            left = 0
            right = cols - 1

            while left < right:
                if grid[r][left] != grid[r][right]:
                    row_flips += 1

                left += 1
                right -= 1

        col_flips = 0

        # Count flips needed to make all columns palindromic
        for c in range(cols):
            top = 0
            bottom = rows - 1

            while top < bottom:
                if grid[top][c] != grid[bottom][c]:
                    col_flips += 1

                top += 1
                bottom -= 1

        return min(row_flips, col_flips)

The implementation follows the exact logic described in the algorithm walkthrough.

First, we compute the number of mismatched mirrored pairs across all rows. Two pointers are used:

left
right

They move inward until all mirrored positions are checked.

Whenever the values differ, we increment row_flips because one flip is sufficient to fix that pair.

Next, we repeat the same process vertically for columns using:

top
bottom

Again, every mismatch contributes exactly one required flip.

Finally, we return the smaller of the two totals because the problem only requires one of the two conditions to be satisfied.

Go Solution

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

    rowFlips := 0

    // Count flips needed for palindromic rows
    for r := 0; r < rows; r++ {
        left := 0
        right := cols - 1

        for left < right {
            if grid[r][left] != grid[r][right] {
                rowFlips++
            }

            left++
            right--
        }
    }

    colFlips := 0

    // Count flips needed for palindromic columns
    for c := 0; c < cols; c++ {
        top := 0
        bottom := rows - 1

        for top < bottom {
            if grid[top][c] != grid[bottom][c] {
                colFlips++
            }

            top++
            bottom--
        }
    }

    if rowFlips < colFlips {
        return rowFlips
    }

    return colFlips
}

The Go implementation mirrors the Python logic closely.

A few Go-specific details are worth noting:

Go does not provide a built-in min function for integers, so we use a simple conditional comparison.
The grid is represented as [][]int, where each inner slice corresponds to a row.
Integer overflow is not a concern because the maximum number of flips is at most m * n, which is bounded by 200000.

Worked Examples

Example 1

Input

grid = [
    [1,0,0],
    [0,0,0],
    [0,0,1]
]

Row Palindrome Calculation

We check mirrored pairs in each row.

Row	Compared Cells	Match?	Flips Added
[1,0,0]	1 vs 0	No	1
[0,0,0]	0 vs 0	Yes	0
[0,0,1]	0 vs 1	No	1

Total:

row_flips = 2

Column Palindrome Calculation

Column	Compared Cells	Match?	Flips Added
[1,0,0]	1 vs 0	No	1
[0,0,0]	0 vs 0	Yes	0
[0,0,1]	0 vs 1	No	1

Total:

col_flips = 2

Answer:

min(2, 2) = 2

Example 2

Input

grid = [
    [0,1],
    [0,1],
    [0,0]
]

Row Palindrome Calculation

Row	Compared Cells	Match?	Flips Added
[0,1]	0 vs 1	No	1
[0,1]	0 vs 1	No	1
[0,0]	0 vs 0	Yes	0

Total:

row_flips = 2

Column Palindrome Calculation

Column 0:

[0,0,0]

Mirrored comparison:

0 vs 0

No flip needed.

Column 1:

[1,1,0]

Mirrored comparison:

1 vs 0

One flip needed.

Total:

col_flips = 1

Answer:

min(2, 1) = 1

Example 3

Input

grid = [
    [1],
    [0]
]

Every row has length 1, so each row is automatically palindromic.

row_flips = 0

Column:

[1,0]

Mirrored comparison:

1 vs 0

One flip needed.

col_flips = 1

Answer:

min(0, 1) = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m * n)	Every cell participates in at most one mirrored comparison for rows and one for columns
Space	O(1)	Only a few counters and pointers are used

The algorithm efficiently scans the grid without creating auxiliary data structures. Each mirrored pair is processed exactly once, making the runtime linear in the size of the input.

Test Cases

from typing import List

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

        row_flips = 0

        for r in range(rows):
            left = 0
            right = cols - 1

            while left < right:
                if grid[r][left] != grid[r][right]:
                    row_flips += 1

                left += 1
                right -= 1

        col_flips = 0

        for c in range(cols):
            top = 0
            bottom = rows - 1

            while top < bottom:
                if grid[top][c] != grid[bottom][c]:
                    col_flips += 1

                top += 1
                bottom -= 1

        return min(row_flips, col_flips)

sol = Solution()

# Example 1
assert sol.minFlips([
    [1,0,0],
    [0,0,0],
    [0,0,1]
]) == 2  # both options require 2 flips

# Example 2
assert sol.minFlips([
    [0,1],
    [0,1],
    [0,0]
]) == 1  # columns are cheaper

# Example 3
assert sol.minFlips([
    [1],
    [0]
]) == 0  # single-cell rows are already palindromic

# Already palindromic rows
assert sol.minFlips([
    [1,0,1],
    [0,1,0]
]) == 0  # no flips needed

# Already palindromic columns
assert sol.minFlips([
    [1,0],
    [0,1],
    [1,0]
]) == 0  # columns already symmetric

# Single row
assert sol.minFlips([
    [1,0,0,1]
]) == 0  # row already palindrome

# Single column
assert sol.minFlips([
    [1],
    [0],
    [1]
]) == 0  # column already palindrome

# One mismatch in row
assert sol.minFlips([
    [1,0,1,1]
]) == 1  # fix one mirrored mismatch

# Large asymmetric case
assert sol.minFlips([
    [1,0,0,0],
    [0,1,1,1],
    [1,1,0,0]
]) == 3  # verifies general behavior

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

Test Summary

Test	Why
Example 1	Verifies standard mixed-case behavior
Example 2	Ensures column option can be better
Example 3	Tests single-column edge case
Already palindromic rows	Confirms zero flips are detected
Already palindromic columns	Confirms column symmetry handling
Single row	Tests horizontal palindrome logic
Single column	Tests vertical palindrome logic
One mismatch in row	Validates single-pair correction
Large asymmetric case	Tests general non-trivial behavior
All zeros	Verifies uniform grid handling

Edge Cases

Single Row Grid

If the grid contains only one row, then every column has only one element and is automatically palindromic. A buggy implementation might still attempt invalid mirrored comparisons vertically.

This implementation handles the case naturally because:

while top < bottom

never executes when there is only one row.

Single Column Grid

If the grid contains only one column, then every row is automatically palindromic because a single character always reads the same forward and backward.

The row comparison loop safely skips work because:

left < right

is false immediately.

Odd-Length Rows or Columns

When a row or column has odd length, the middle element has no mirrored partner.

For example:

[1, 0, 1]

The center 0 never needs modification because it mirrors itself.

Using two pointers that stop when they meet ensures the middle element is ignored correctly.

Completely Symmetric Grid

A fully symmetric grid should return 0.

Some implementations accidentally overcount by comparing pairs twice.

This solution avoids double counting because it only processes half of each row and half of each column.

Completely Asymmetric Grid

A grid where every mirrored pair mismatches tests whether the implementation correctly counts each pair exactly once.

Because every mismatch contributes exactly one flip, the algorithm produces the precise minimum without unnecessary operations.