Problem Description

You have a binary matrix grid with dimensions m x n containing only 0s and 1s.

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

You can flip any cell in the grid, changing a 0 to 1 or a 1 to 0.

Your goal is to make either all rows palindromic or all columns palindromic, using the minimum number of flips possible.

Return the minimum number of cells that need to be flipped to achieve this.

For example, if you have a row [1, 0, 1], it's already palindromic. But a row [1, 0, 0] would need one flip (either change the first cell to 0 or the last cell to 1) to become palindromic.

The solution works by:

1. Counting how many flips are needed to make all rows palindromic (cnt1)
2. Counting how many flips are needed to make all columns palindromic (cnt2)
3. Returning the minimum of these two counts

For each row, we compare pairs of elements from opposite ends (first with last, second with second-last, etc.) and count mismatches. The same process is applied to columns. Since we need to choose between making all rows palindromic OR all columns palindromic, we take the option that requires fewer flips.

Intuition

The key insight is that we have two independent choices: make all rows palindromic OR make all columns palindromic. We don't need to do both, so we can calculate the cost of each option separately and pick the cheaper one.

For a sequence to be palindromic, elements at symmetric positions must be equal. For a row with n elements, position 0 must equal position n-1, position 1 must equal position n-2, and so on. When these positions don't match, we need exactly one flip to fix the mismatch (we can flip either position to match the other).

Since flipping a cell only affects its own row and column, making rows palindromic doesn't interfere with making other rows palindromic. The same applies to columns. This independence means we can simply count the total mismatches across all rows (or all columns) to get the total flips needed.

The counting process only needs to check half of each row or column because we're comparing pairs. For a row of length n, we only need to check the first n//2 positions against their mirror positions. Each mismatch we find represents exactly one required flip.

By calculating both cnt1 (flips needed for all rows) and cnt2 (flips needed for all columns), we can choose the option with fewer flips, giving us the optimal solution. This greedy approach works because the two options are mutually exclusive - we only need to satisfy one condition, not both.

Learn more about Two Pointers patterns.

Solution Approach

The implementation uses a straightforward counting approach with two separate passes through the grid.

Step 1: Initialize counters and get dimensions

m, n = len(grid), len(grid[0])
cnt1 = cnt2 = 0

We store the grid dimensions and initialize two counters: cnt1 for row flips and cnt2 for column flips.

Step 2: Count flips needed for all rows to be palindromic

for row in grid:
    for j in range(n // 2):
        if row[j] != row[n - j - 1]:
            cnt1 += 1

For each row, we iterate through the first half of elements (j from 0 to n//2 - 1). We compare each element at position j with its mirror element at position n - j - 1. If they don't match, we increment cnt1. We only check half the row because each comparison covers a pair of positions.

Step 3: Count flips needed for all columns to be palindromic

for j in range(n):
    for i in range(m // 2):
        if grid[i][j] != grid[m - i - 1][j]:
            cnt2 += 1

For each column j, we iterate through the first half of rows (i from 0 to m//2 - 1). We compare the element at row i with its mirror element at row m - i - 1 in the same column. Mismatches increment cnt2.

Step 4: Return the minimum

return min(cnt1, cnt2)

Since we need either all rows OR all columns to be palindromic (not both), we return the smaller count.

The time complexity is O(m * n) as we traverse the entire grid twice. The space complexity is O(1) since we only use two counter variables regardless of input size.

Example Walkthrough

Let's walk through a small example with a 3x3 grid:

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

Step 1: Count flips to make all rows palindromic (cnt1)

Row 0: [1, 0, 0]

• Compare position 0 with position 2: 1 != 0 → mismatch, need 1 flip
• Position 1 (middle) doesn't need comparison
• Running total: cnt1 = 1

Row 1: [0, 1, 1]

• Compare position 0 with position 2: 0 != 1 → mismatch, need 1 flip
• Running total: cnt1 = 2

Row 2: [1, 1, 0]

• Compare position 0 with position 2: 1 != 0 → mismatch, need 1 flip
• Running total: cnt1 = 3

Step 2: Count flips to make all columns palindromic (cnt2)

Column 0: [1, 0, 1] (reading top to bottom)

• Compare position 0 with position 2: 1 == 1 → match, no flip needed
• Running total: cnt2 = 0

Column 1: [0, 1, 1]

• Compare position 0 with position 2: 0 != 1 → mismatch, need 1 flip
• Running total: cnt2 = 1

Column 2: [0, 1, 0]

• Compare position 0 with position 2: 0 == 0 → match, no flip needed
• Running total: cnt2 = 1

Step 3: Return minimum

• cnt1 = 3 (flips to make all rows palindromic)
• cnt2 = 1 (flips to make all columns palindromic)
• Return min(3, 1) = 1

The optimal solution is to make all columns palindromic with just 1 flip. We could flip grid[0][1] from 0 to 1 (or grid[2][1] from 1 to 0) to make column 1 palindromic: [1, 1, 1] or [0, 0, 0].

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n), where m is the number of rows and n is the number of columns in the matrix grid.

The algorithm consists of two main parts:

• First loop: Iterates through all m rows, and for each row, checks n/2 pairs of elements. This results in O(m × n/2) operations.
• Second loop: Iterates through all n columns, and for each column, checks m/2 pairs of elements. This results in O(n × m/2) operations.

The total time complexity is O(m × n/2) + O(n × m/2) = O(m × n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space for variables m, n, cnt1, cnt2, and loop counters i and j. No additional data structures that scale with input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Counting Total Flips Instead of Minimum Required

A common mistake is thinking that when two elements don't match (e.g., row[j] != row[n-j-1]), you need to flip both of them. This leads to counting 2 flips per mismatch instead of 1.

Incorrect approach:

for row in grid:
    for j in range(n // 2):
        if row[j] != row[n - j - 1]:
            cnt1 += 2  # WRONG: Only need to flip one element

Why it's wrong: When making a palindrome, if position j has value 1 and position n-j-1 has value 0, you only need to flip ONE of them to make them match. You can either flip the 1 to 0 OR flip the 0 to 1.

Correct approach: Count 1 flip per mismatched pair, as shown in the original solution.

2. Double-Counting Middle Elements in Odd-Length Rows/Columns

When a row or column has odd length, there's a middle element that doesn't have a pair. Some might incorrectly try to include it in the palindrome check.

Incorrect approach:

for row in grid:
    for j in range((n + 1) // 2):  # WRONG: May process middle element
        if row[j] != row[n - j - 1]:
            cnt1 += 1

Why it's wrong: For odd-length arrays, the middle element (at index n//2) is compared with itself when j = n//2, resulting in row[n//2] != row[n//2] which is always false. While this doesn't affect correctness, it's unnecessary computation.

Correct approach: Use range(n // 2) which automatically excludes the middle element in odd-length cases, since the middle element is already palindromic by definition.

3. Attempting to Optimize by Making Both Rows AND Columns Palindromic

Some might think they can find an optimal solution that makes both rows and columns palindromic simultaneously.

Why it's wrong: The problem asks for EITHER all rows OR all columns to be palindromic, not both. Trying to achieve both simultaneously would likely require more flips and isn't what the problem asks for.

Correct approach: Calculate the minimum flips for rows and columns separately, then return the smaller value.