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 either all rows palindromic or all columns palindromic.
Example 1:
Input: grid = [[1,0,0],[0,0,0],[0,0,1]]
Output: 2
Explanation:
Flipping the highlighted cells makes all the rows palindromic.
Example 2:
Input: grid = [[0,1],[0,1],[0,0]]
Output: 1
Explanation:
Flipping the highlighted cell makes all the columns palindromic.
Example 3:
Input: grid = [[1],[0]]
Output: 0
Explanation:
All rows are already palindromic.
Constraints:
m == grid.lengthn == grid[i].length1 <= m * n <= 2 * 1050 <= grid[i][j] <= 1Problem Overview: You are given a binary matrix. A row or column is palindromic if reading it from left-to-right equals right-to-left. The task is to compute the minimum number of cell flips needed so that either every row becomes palindromic or every column becomes palindromic.
Approach 1: Greedy Row/Column Two-Pointer Scan (O(m*n) time, O(1) space)
The grid can be fixed in two independent ways: make all rows palindromic or make all columns palindromic. For rows, iterate each row and use the classic two pointers technique. Start one pointer at the left and one at the right. If grid[r][l] and grid[r][r] differ, one flip is required to make the pair equal. Count mismatches for every symmetric pair and sum them across rows. The same idea applies to columns: scan each column with pointers from top and bottom and count mismatched pairs.
The key observation: every symmetric pair must contain identical values for the row or column to be palindromic. Flipping either cell resolves the mismatch, so each mismatch contributes exactly one flip. Compute the total flips needed for rows and the total for columns, then return the smaller value. This greedy counting works because each pair is independent and there is no cross-pair dependency.
This method uses only simple iteration over the array structure representing the grid. No extra memory or preprocessing is required, which keeps the implementation short and efficient.
Approach 2: Dynamic Programming Pair Aggregation (O(m*n) time, O(1) space)
A DP-style interpretation treats every symmetric pair as a small subproblem. For a row, the pair (i, j) and (i, n-1-j) must end with the same value. The minimum flips for the pair is 0 if the values already match and 1 otherwise. A DP transition simply accumulates the optimal cost for each processed pair. Repeating this across all rows produces the total row cost; repeating across columns produces the column cost.
Although labeled as dynamic programming, the state transition collapses to a direct mismatch count because each pair decision is independent. The DP framing can still help when reasoning about extensions of the problem (for example when flips have different costs or when multiple constraints interact).
Recommended for interviews: The greedy two-pointer approach is the expected solution. It demonstrates clear reasoning about symmetry and efficient traversal of a matrix. A brute-force mindset would attempt flipping cells and rechecking palindromes, but recognizing that only symmetric pairs matter reduces the problem to a linear scan. Interviewers typically look for this observation and an O(m*n) implementation.
This approach focuses on checking each row and each column to calculate the number of flips required to make them palindromic.
For rows, iterate through half of the row. For each element, compare it with its corresponding element from the opposite end. If they differ, increment the flip counter.
Repeat the process for each column and compute the minimum flips needed for each column. Finally, return the minimum flips between making all rows palindromic and all columns palindromic.
Here, we define a helper function flips_for_palindrome to calculate the minimum number of flips required to make an array palindromic.
We calculate the flip counts for all rows and all columns using this helper and return the minimum between the two.
Time Complexity: O(m * n), where m and n are the dimensions of the grid. This is because we iterate through each element once to calculate flips for rows and columns.
Space Complexity: O(1), as we use constant extra space for counting flips.
Utilizing dynamic programming (DP) techniques, we can compute minimum flips needed to make binary sequences palindromic once and store the results to reuse for each row and column.
This involves first pre-calculating the cost of flips for sequences of possible lengths which speeds up the process of determining minimum flips for rows and columns.
In Java, similar logic is applied. We determine necessary flips for all rows and columns using two arrays: rowFlips and colFlips.
Each position's flips are calculated once and stored for efficient retrieval during comparisons.
Time Complexity: O(m * n), as each cell is processed once to compute the flip values.
Space Complexity: O(m + n), used by the arrays storing flips for rows and columns.
We separately count the number of flips for rows and columns, denoted as cnt1 and cnt2, respectively. Finally, we take the minimum of the two.
The time complexity is O(m times n), where m and n are the number of rows and columns of the matrix grid, respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach for Rows or Columns | Time Complexity: O(m * n), where m and n are the dimensions of the grid. This is because we iterate through each element once to calculate flips for rows and columns. Space Complexity: O(1), as we use constant extra space for counting flips. |
| Dynamic Programming Approach | Time Complexity: O(m * n), as each cell is processed once to compute the flip values. Space Complexity: O(m + n), used by the arrays storing flips for rows and columns. |
| Counting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Two-Pointer Scan (Rows vs Columns) | O(m*n) | O(1) | Best general solution. Directly counts mismatched symmetric pairs in rows and columns. |
| Dynamic Programming Pair Aggregation | O(m*n) | O(1) | Useful for reasoning about symmetric pair costs or when extending the problem with additional constraints. |
Minimum Number of Flips to Make Binary Grid Palindromic I | Biweekly Contest 136 | Leetcode Solution • codi • 1,252 views views
Watch 6 more video solutions →Practice Minimum Number of Flips to Make Binary Grid Palindromic I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor