Minimum Number of Flips to Make Binary Grid Palindromic II solution and explanation
Google
9 more videos on this problem
DP Solution | Minimum Number of Flips to Make Binary Grid Palindromic II | With ExamplesCodeNow - By Gopal Gupta · 19:47 · 1K views
3240. Minimum Number of Flips to Make Binary Grid Palindromic II (Leetcode Medium)Programming Live with Larry · 43:08 · 932 views
Minimum Number of Flips to Make Binary Grid Palindromic II Solution | LEETCODE BIWEEKLY CONTEST 136JUST CODE · 1:58 · 821 views
Leetcode 3240 | Minimum Number of Flips to Make Binary Grid Palindromic II | Biweekly Contest 136Road To FAANG · 16:04 · 809 views
Leetcode | Biweekly Contest 136 | 3240 | Minimum Number of Flips to Make Binary Grid Palindromic IIPretest Passed · 26:08 · 696 views
3240. Minimum Number of Flips to Make Binary Grid Palindromic IITech Courses · 22:15 · 516 views
LeetCode Biweekly Contest 136 | Minimum Number of Flips to Make Binary Grid Palindromic IISmart Interviews · 30:24 · 400 views
Minimum Number of Flips to Make Binary Grid Palindromic IIJoyjit Codes · 8:19 · 342 views
Minimum Number of Flips to Make Binary Grid Palindromic II | LeetCode | Approach and sol#code_craze · 13:56 · 27 views
Minimum Number of Flips to Make Binary Grid Palindromic II | Leetcode 3240 | MediumAshutosh Agrawal · 15:47 · 21 views
The problem
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] <= 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.
def min_flips(grid):
m, n = len(grid), len(grid[0])
count = 0
for i in range(m):
for j in range(n // 2):
if grid[i][j] != grid[i][n - j - 1]:
count += 1
for j in range(n):
for i in range(m // 2):
if grid[i][j] != grid[m - i - 1][j]:
count += 1
one_count = sum(sum(row) for row in grid)
return count, ((4 - one_count % 4) % 4)
grid = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
print(min_flips(grid))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.
Time Complexity: O(m * n)
Space Complexity: O(1)
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.
function minFlips(grid) {
let m = grid.length, n = grid[0].length;
let count = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < Math.floor(n / 2); j++) {
if (grid[i][j] !== grid[i][n - j - 1]) count++;
}
}
for (let j = 0; j < n; j++) {
for (let i = 0; i < Math.floor(m / 2); i++) {
if (grid[i][j] !== grid[m - i - 1][j]) count++;
}
}
let oneCount = grid.flat().reduce((acc, val) => acc + val, 0);
return [count, (4 - oneCount % 4) % 4];
}
const gridExample = [[1,0,0],[0,1,0],[0,0,1]];
console.log(minFlips(gridExample));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.
Time Complexity: O(m * n)
Space Complexity: O(1)
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.
def minFlipsToPalindromic(grid):
m, n = len(grid), len(grid[0])
flips = 0
totalOnes = 0
for i in range(m):
for j in range(n // 2):
if grid[i][j] != grid[i][n - 1 - j]:
flips += 1
for j in range(n):
for i in range(m // 2):
if grid[i][j] != grid[m - 1 - i][j]:
flips += 1
totalOnes = m * n - flips
if totalOnes % 4 != 0:
flips += (4 - totalOnes % 4)
return flips
grid = [[1,0,0],[0,1,0],[0,0,1]]
print(minFlipsToPalindromic(grid))public class BinaryGrid {
public static int minFlipsToPalindromic(int[][] grid) {
int flips = 0;
int m = grid.length, n = grid[0].length;
int totalOnes = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n / 2; j++) {
if (grid[i][j] != grid[i][n - 1 - j]) flips++;
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < m / 2; i++) {
if (grid[i][j] != grid[m - 1 - i][j]) flips++;
}
}
totalOnes = m * n - flips;
if (totalOnes % 4 != 0) flips += (4 - totalOnes % 4);
return flips;
}
public static void main(String[] args) {
int[][] grid = {{1,0,0},{0,1,0},{0,0,1}};
System.out.println(minFlipsToPalindromic(grid));
}
}#include <iostream>
#include <vector>
using namespace std;
int minFlipsToPalindromic(vector<vector<int>>& grid) {
int flips = 0, totalOnes = 0, m = grid.size(), n = grid[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n / 2; j++) {
if (grid[i][j] != grid[i][n - 1 - j]) flips++;
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < m / 2; i++) {
if (grid[i][j] != grid[m - 1 - i][j]) flips++;
}
}
totalOnes = m * n - flips;
if (totalOnes % 4 != 0) flips += (4 - totalOnes % 4);
return flips;
}
int main() {
vector<vector<int>> grid = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
cout << minFlipsToPalindromic(grid) << endl;
return 0;
}function minFlipsToPalindromic(grid) {
const m = grid.length, n = grid[0].length;
let flips = 0;
let totalOnes = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < Math.floor(n / 2); j++) {
if (grid[i][j] !== grid[i][n - 1 - j]) flips++;
}
}
for (let j = 0; j < n; j++) {
for (let i = 0; i < Math.floor(m / 2); i++) {
if (grid[i][j] !== grid[m - 1 - i][j]) flips++;
}
}
totalOnes = m * n - flips;
if (totalOnes % 4 !== 0) flips += (4 - totalOnes % 4);
return flips;
}
const grid = [[1, 0, 0], [0, 1, 0], [0, 0, 1]];
console.log(minFlipsToPalindromic(grid));#include <stdio.h>
#include <stdlib.h>
int minFlipsToPalindromic(int** grid, int m, int n) {
int flips = 0, totalOnes = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n / 2; j++) {
if (grid[i][j] != grid[i][n - 1 - j]) flips++;
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < m / 2; i++) {
if (grid[i][j] != grid[m - 1 - i][j]) flips++;
}
}
// Adjust flips for central elements
totalOnes = m * n - flips;
if (totalOnes % 4 != 0) flips += (4 - totalOnes % 4);
return flips;
}
int main() {
int m = 3, n = 3;
int grid[3][3] = {{1,0,0},{0,1,0},{0,0,1}};
int* gridPtrs[3] = {grid[0], grid[1], grid[2]};
printf("%d\n", minFlipsToPalindromic(gridPtrs, m, n));
return 0;
}using System;
public class GridFlip {
public static int MinFlipsToPalindromic(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
int flips = 0, totalOnes = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n / 2; j++) {
if (grid[i][j] != grid[i][n - 1 - j]) flips++;
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < m / 2; i++) {
if (grid[i][j] != grid[m - 1 - i][j]) flips++;
}
}
totalOnes = m * n - flips;
if (totalOnes % 4 != 0) flips += (4 - totalOnes % 4);
return flips;
}
public static void Main() {
int[][] grid = new int[][] {
new int[] {1, 0, 0},
new int[] {0, 1, 0},
new int[] {0, 0, 1}
};
Console.WriteLine(MinFlipsToPalindromic(grid));
}
}Python code handles grid flipping by checking symmetry in a similar manner to other solutions, leveraging Python's easy list manipulation features.
Time complexity: O(m*n), Space complexity: O(1).
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.
def minFlipsToPalindromic(grid):
m, n = len(grid), len(grid[0])
flips = 0
totalOnes = 0
for i in range(m):
for j in range(n // 2):
if grid[i][j] != grid[i][n - 1 - j]:
flips += 1
for j in range(n):
for i in range(m // 2):
if grid[i][j] != grid[m - 1 - i][j]:
flips += 1
totalOnes = m * n - flips
if totalOnes % 4 != 0:
flips += (4 - totalOnes % 4) & 3
return flips
grid = [[1,0,0],[0,1,0],[0,0,1]]
print(minFlipsToPalindromic(grid))public class BinaryGridWithDiv {
public static int minFlipsToPalindromic(int[][] grid) {
int m = grid.length, n = grid[0].length;
int flips = 0, totalOnes = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n / 2; j++) {
if (grid[i][j] != grid[i][n - 1 - j]) flips++;
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < m / 2; i++) {
if (grid[i][j] != grid[m - 1 - i][j]) flips++;
}
}
totalOnes = m * n - flips;
if (totalOnes % 4 != 0) flips += ((4 - totalOnes % 4) & 3);
return flips;
}
public static void main(String[] args) {
int[][] grid = {{1,0,0},{0,1,0},{0,0,1}};
System.out.println(minFlipsToPalindromic(grid));
}
}#include <iostream>
#include <vector>
using namespace std;
int minFlipsToPalindromic(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int flips = 0, totalOnes = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n / 2; j++) {
if (grid[i][j] != grid[i][n - 1 - j]) flips++;
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < m / 2; i++) {
if (grid[i][j] != grid[m - 1 - i][j]) flips++;
}
}
totalOnes = m * n - flips;
if ((totalOnes % 4) != 0) flips += ((4 - totalOnes % 4) & 3);
return flips;
}
int main() {
vector<vector<int>> grid = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
cout << minFlipsToPalindromic(grid) << endl;
return 0;
}function minFlipsToPalindromic(grid) {
const m = grid.length, n = grid[0].length;
let flips = 0;
let totalOnes = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < Math.floor(n / 2); j++) {
if (grid[i][j] !== grid[i][n - 1 - j]) flips++;
}
}
for (let j = 0; j < n; j++) {
for (let i = 0; i < Math.floor(m / 2); i++) {
if (grid[i][j] !== grid[m - 1 - i][j]) flips++;
}
}
totalOnes = m * n - flips;
if (totalOnes % 4 !== 0) flips += ((4 - totalOnes % 4) & 3);
return flips;
}
const grid = [[1, 0, 0], [0, 1, 0], [0, 0, 1]];
console.log(minFlipsToPalindromic(grid));#include <stdio.h>
#include <stdlib.h>
int minFlipsToPalindromic(int** grid, int m, int n) {
int flips = 0;
int totalOnes = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n / 2; j++) {
if (grid[i][j] != grid[i][n - 1 - j]) flips++;
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < m / 2; i++) {
if (grid[i][j] != grid[m - 1 - i][j]) flips++;
}
}
totalOnes = m * n - flips;
if ((totalOnes % 4) != 0) flips += ((4 - totalOnes % 4) & 3);
return flips;
}
int main() {
int m = 3, n = 3;
int grid[3][3] = {{1,0,0},{0,1,0},{0,0,1}};
int* gridPtrs[3] = {grid[0], grid[1], grid[2]};
printf("%d\n", minFlipsToPalindromic(gridPtrs, m, n));
return 0;
}using System;
public class GridFlipBitManipulation {
public static int MinFlipsToPalindromic(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
int flips = 0, totalOnes = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n / 2; j++) {
if (grid[i][j] != grid[i][n - 1 - j]) flips++;
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < m / 2; i++) {
if (grid[i][j] != grid[m - 1 - i][j]) flips++;
}
}
totalOnes = m * n - flips;
if (totalOnes % 4 != 0) flips += ((4 - totalOnes % 4) & 3);
return flips;
}
public static void Main() {
int[][] grid = new int[][] {
new int[] {1, 0, 0},
new int[] {0, 1, 0},
new int[] {0, 0, 1}
};
Console.WriteLine(MinFlipsToPalindromic(grid));
}
}This Python solution incorporates bitwise operations to minimize and adjust flips, aligning with the grid's constraints efficiently.
Time complexity: O(m*n), Space complexity: O(1).
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
mandnare even, we directly return the answer. - If both
mandnare odd, the center cell must be0because the number of1s must be divisible by4. - If
mis odd andnis even, we need to consider the middle row. - If
mis even andnis 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 thediffcells to0, and the number of operations isdiff. - Otherwise, if
cnt1 = 2, ifdiff \gt 0, we can change one of the cells to1to makecnt1 = 4, and then change the remainingdiff - 1cells to0. The total number of operations isdiff. - Otherwise, if
diff = 0, we change the2cells to0to makecnt1 bmod 4 = 0, and the number of operations is2.
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).
function minFlips(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
let ans = 0;
for (let i = 0; i < Math.floor(m / 2); i++) {
for (let j = 0; j < Math.floor(n / 2); j++) {
const x = m - i - 1;
const y = n - j - 1;
const cnt1 = grid[i][j] + grid[x][j] + grid[i][y] + grid[x][y];
ans += Math.min(cnt1, 4 - cnt1);
}
}
if (m % 2 === 1 && n % 2 === 1) {
ans += grid[Math.floor(m / 2)][Math.floor(n / 2)];
}
let diff = 0,
cnt1 = 0;
if (m % 2 === 1) {
for (let j = 0; j < Math.floor(n / 2); j++) {
if (grid[Math.floor(m / 2)][j] === grid[Math.floor(m / 2)][n - j - 1]) {
cnt1 += grid[Math.floor(m / 2)][j] * 2;
} else {
diff += 1;
}
}
}
if (n % 2 === 1) {
for (let i = 0; i < Math.floor(m / 2); i++) {
if (grid[i][Math.floor(n / 2)] === grid[m - i - 1][Math.floor(n / 2)]) {
cnt1 += grid[i][Math.floor(n / 2)] * 2;
} else {
diff += 1;
}
}
}
ans += cnt1 % 4 === 0 || diff > 0 ? diff : 2;
return ans;
}func minFlips(grid [][]int) int {
m, n := len(grid), len(grid[0])
ans := 0
for i := 0; i < m/2; i++ {
for j := 0; j < n/2; j++ {
x, y := m-i-1, n-j-1
cnt1 := grid[i][j] + grid[x][j] + grid[i][y] + grid[x][y]
ans += min(cnt1, 4-cnt1)
}
}
if m%2 == 1 && n%2 == 1 {
ans += grid[m/2][n/2]
}
diff, cnt1 := 0, 0
if m%2 == 1 {
for j := 0; j < n/2; j++ {
if grid[m/2][j] == grid[m/2][n-j-1] {
cnt1 += grid[m/2][j] * 2
} else {
diff += 1
}
}
}
if n%2 == 1 {
for i := 0; i < m/2; i++ {
if grid[i][n/2] == grid[m-i-1][n/2] {
cnt1 += grid[i][n/2] * 2
} else {
diff += 1
}
}
}
if cnt1%4 == 0 || diff > 0 {
ans += diff
} else {
ans += 2
}
return ans
}Complexity comparison
| 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). |
| Bit Manipulation for Divisibility Adjustment | Time complexity: O(m*n), Space complexity: O(1). |
| Case Analysis | – |
Complexity 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 |
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.