Skip to main content
Talentd

Minimum Number of Flips to Make Binary Grid Palindromic II - Solution & Explanation

MediumArrayTwo PointersMatrix25 min readAsked at: Google
Practice this problem

Problem Statement

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 all rows and columns palindromic, and the total number of 1's in grid divisible by 4.

 

Example 1:

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

Output: 3

Explanation:

Example 2:

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

Output: 2

Explanation:

Example 3:

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

Output: 2

Explanation:

 

Constraints:

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

Approach Overview

Problem Overview: You are given a binary m x n grid. The goal is to flip the minimum number of cells so the grid becomes palindromic with respect to both horizontal and vertical symmetry constraints. Cells that mirror each other across the center must end up with the same value.

Approach 1: Symmetric Mirroring Method (O(m*n) time, O(1) space)

The key observation is that four cells linked by horizontal and vertical symmetry must share the same value. For any position (i, j), its mirrored group contains (i, j), (i, n-1-j), (m-1-i, j), and (m-1-i, n-1-j). Count how many of these are 1s and 0s, then flip the minority to match the majority. Iterate only through the top-left quadrant to avoid double counting. When the grid has a middle row or column, handle those symmetric pairs separately.

Approach 2: Grid Sweeping with Minimum Operations (O(m*n) time, O(1) space)

This approach sweeps the grid while evaluating symmetric constraints directly. For each cell group determined by reflection across the center, compute the minimum number of flips required to make the values equal. The sweep processes four-cell groups first, then two-cell groups in the middle row or column when dimensions are odd. The algorithm accumulates the minimal operations during traversal without additional storage, which keeps space usage constant.

Approach 3: Mirror-based Flip Strategy (O(m*n) time, O(1) space)

This strategy explicitly models the mirror relationships using index arithmetic. For every symmetric group, count the number of 1s and determine the minimal flips needed to make the group uniform. Groups of four cost min(ones, 4 - ones) flips. Special handling is required for the center cell (when both dimensions are odd) and for pairs along the middle row or column. The approach is simple to implement and works well with Array traversal and Matrix index manipulation.

Approach 4: Bit Manipulation for Divisibility Adjustment (O(m*n) time, O(1) space)

After processing symmetric groups, some implementations enforce additional parity constraints using bit manipulation. Counts of ones in special symmetric regions are adjusted so the resulting configuration satisfies divisibility conditions derived from mirror symmetry. Bitwise checks make these adjustments efficient. This method is mainly useful when implementing the solution in low-level languages and optimizing constant factors.

Recommended for interviews: The mirror-based grouping solution is what most interviewers expect. Start by explaining the symmetry insight: every cell belongs to a mirrored group of size four or two. Demonstrating the brute reasoning about symmetry shows understanding, while implementing the O(m*n) mirror strategy proves you can translate the observation into an efficient algorithm using simple Two Pointers-style mirrored indexing.

Approach 1: Symmetric Mirroring Method

To achieve a palindromic grid, we need to make each row and each column a palindrome. We need to find the minimum number of changes required for each combination of symmetric pairs for every row and column.

We iterate through only half of every row and every column and count the discrepancies in the mirrored positions. This allows us to minimize the overall number of changes required.

Code

Python

Python

Complexity

Time Complexity: O(m * n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Grid Sweeping with Minimum Operations

This method focuses on fixing palindromic properties row by row and column by column. By iterating through each row and column and considering each element and its symmetric counterpart, the grid is adjusted to minimize operations.

This method iterates through the grid, checking for palindromic properties for each row and column. The function accounts not only for the symmetry but also for adjusting the total count of '1's for divisibility by 4.

Code

JavaScript

JavaScript

Complexity

Time Complexity: O(m * n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Mirror-based Flip Strategy

This approach focuses on identifying and correcting mismatched positions in each row and column to make them palindromic. By analyzing each row and column, flips are determined based on the differences from their mirrored indices.

The C program above counts the number of mismatches in each row and column and computes flips accordingly. Adjustments are made to ensure the number of ones is divisible by 4 by adding more flips if necessary.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(m*n), Space complexity: O(1) due to in-place calculations.

Try this approach in the editor →

Approach 4: Bit Manipulation for Divisibility Adjustment

This approach extends to use bit manipulation to adjust the counts of ones. Strategies include toggling bits at strategic positions to achieve divisibility by 4 without excessive flips, leveraging the innate binary nature of the grid.

This C code calculates mismatches but uses bit manipulation to adjust the number of ones for divisibility by 4 more cleverly, using logical operators.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity: O(m*n), Space complexity: O(1).

Try this approach in the editor →

Approach 5: Case Analysis

If both rows and columns are palindromic, then for any i \in [0, m / 2) and j \in [0, n / 2), it must satisfy grid[i][j] = grid[m - i - 1][j] = grid[i][n - j - 1] = grid[m - i - 1][n - j - 1]. They must either all become 0 or all become 1. The number of changes to 0 is c_0 = grid[i][j] + grid[m - i - 1][j] + grid[i][n - j - 1] + grid[m - i - 1][n - j - 1], and the number of changes to 1 is c_1 = 4 - c_0. We take the minimum of the two and add it to the answer.

Next, we discuss the parity of m and n:

  • If both m and n are even, we directly return the answer.
  • If both m and n are odd, the center cell must be 0 because the number of 1s must be divisible by 4.
  • If m is odd and n is even, we need to consider the middle row.
  • If m is even and n is odd, we need to consider the middle column.

For the latter two cases, we need to count the number of differing pairs of cells diff in the middle row or column, and the number of cells that are the same and equal to 1 cnt1. Then we discuss the following cases:

  • If cnt1 bmod 4 = 0, we only need to change the diff cells to 0, and the number of operations is diff .
  • Otherwise, if cnt1 = 2, if diff \gt 0, we can change one of the cells to 1 to make cnt1 = 4, and then change the remaining diff - 1 cells to 0. The total number of operations is diff.
  • Otherwise, if diff = 0, we change the 2 cells to 0 to make cnt1 bmod 4 = 0, and the number of operations is 2.

We add the number of operations to the answer and finally return the answer.

The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Symmetric Mirroring Method

Time Complexity: O(m * n)
Space Complexity: O(1)

Grid Sweeping with Minimum Operations

Time Complexity: O(m * n)
Space Complexity: O(1)

Mirror-based Flip Strategy

Time complexity: O(m*n), Space complexity: O(1) due to in-place calculations.

Bit Manipulation for Divisibility Adjustment

Time complexity: O(m*n), Space complexity: O(1).

Case Analysis—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Symmetric Mirroring MethodO(m*n)O(1)Best general solution using symmetric cell groups
Grid Sweeping with Minimum OperationsO(m*n)O(1)Simple traversal when implementing minimal flip counting directly
Mirror-based Flip StrategyO(m*n)O(1)Most common interview implementation using mirror index pairs
Bit Manipulation for Divisibility AdjustmentO(m*n)O(1)Low-level optimization and parity adjustments in symmetric regions

Video Solution

DP Solution | Minimum Number of Flips to Make Binary Grid Palindromic II | With Examples • CodeNow - By Gopal Gupta • 1,270 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Number of Flips to Make Binary Grid Palindromic II easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 25%. The challenge comes from correctly identifying all symmetric groups and handling edge cases such as the middle row, middle column, and center cell when dimensions are odd.
Minimum Number of Flips to Make Binary Grid Palindromic II Python/Java solution
Most implementations iterate over the top-left quadrant of the grid and process symmetric cell groups. Python, Java, C++, and JavaScript solutions all follow the same logic: compute mirrored indices, count ones in the group, and add the minimum flips needed to make them equal.
How to solve Minimum Number of Flips to Make Binary Grid Palindromic II in O(n)?
Treat symmetric cells as groups defined by reflections across the grid center. For each group of four cells, count the number of ones and flip the minority so all values match. Handle middle row and column pairs separately when dimensions are odd. Since every cell is visited once, the complexity becomes O(m*n).
What is the best approach for Minimum Number of Flips to Make Binary Grid Palindromic II?
The mirror-based symmetric grouping approach is the most efficient. Each cell belongs to a group of up to four symmetric positions formed by horizontal and vertical reflection. By counting how many ones exist in each group and flipping the minority, you minimize operations. The algorithm runs in O(m*n) time with O(1) extra space.
Is Minimum Number of Flips to Make Binary Grid Palindromic II asked at Google/Amazon/Meta?
Matrix symmetry and minimum flip problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations involving palindromic grids, mirrored pairs, or minimum operations on matrices are common because they test indexing logic and algorithmic reasoning.
What data structure is used in Minimum Number of Flips to Make Binary Grid Palindromic II?
The problem primarily uses a 2D array (matrix). The algorithm relies on index calculations to find mirrored positions and counts values inside small symmetric groups. No additional data structures beyond simple counters are required.
What is the time complexity of Minimum Number of Flips to Make Binary Grid Palindromic II?
The optimal solution runs in O(m*n) time because every grid cell is processed once as part of a symmetric group. Space complexity remains O(1) since the algorithm only keeps counters while scanning the matrix.

Ready to solve this problem?

Practice Minimum Number of Flips to Make Binary Grid Palindromic II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays