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.lengthn == grid[i].length1 <= m * n <= 2 * 1050 <= grid[i][j] <= 1Problem 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.
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.
Python
Time Complexity: O(m * n)
Space Complexity: O(1)
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.
JavaScript
Time Complexity: O(m * n)
Space Complexity: O(1)
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.
Time complexity: O(m*n), Space complexity: O(1) due to in-place calculations.
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.
Time complexity: O(m*n), Space complexity: O(1).
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:
m and n are even, we directly return the answer.m and n are odd, the center cell must be 0 because the number of 1s must be divisible by 4.m is odd and n is even, we need to consider the middle row.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:
cnt1 bmod 4 = 0, we only need to change the diff cells to 0, and the number of operations is diff .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.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).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Symmetric Mirroring Method | Time Complexity: O(m * n) |
| Grid Sweeping with Minimum Operations | Time Complexity: O(m * n) |
| 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 | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Symmetric Mirroring Method | O(m*n) | O(1) | Best general solution using symmetric cell groups |
| Grid Sweeping with Minimum Operations | O(m*n) | O(1) | Simple traversal when implementing minimal flip counting directly |
| Mirror-based Flip Strategy | O(m*n) | O(1) | Most common interview implementation using mirror index pairs |
| Bit Manipulation for Divisibility Adjustment | O(m*n) | O(1) | Low-level optimization and parity adjustments in symmetric regions |
DP Solution | Minimum Number of Flips to Make Binary Grid Palindromic II | With Examples • CodeNow - By Gopal Gupta • 1,270 views views
Watch 7 more video solutions →Practice Minimum Number of Flips to Make Binary Grid Palindromic II with our built-in code editor and test cases.
Practice on FleetCode