3240. Minimum Number of Flips to Make Binary Grid Palindromic II LeetCode Solution
In this guide, you will get 3240. Minimum Number of Flips to Make Binary Grid Palindromic II LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Flips to Make Binary Grid Palindromic II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Number of Flips to Make Binary Grid Palindromic II
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.
m == grid.length
n == grid[i].length
1 <= m * n <= 2 * 105
0 <= grid[i][j] <= 1
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(1)
3240. Minimum Number of Flips to Make Binary Grid Palindromic II LeetCode Solution in C++
class Solution {
public:
int minFlips(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
int ans = 0;
int middleOnes = 0;
int mismatchedPairs = 0;
// Handle top-left, top-right, bottom-left, bottom-right cells.
for (int i = 0; i < m / 2; ++i)
for (int j = 0; j < n / 2; ++j) {
const int ones = grid[i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][j] +
grid[m - 1 - i][n - 1 - j];
ans += min(ones, 4 - ones);
}
// Handle the middle row if the number of m is odd.
if (m % 2 == 1)
for (int j = 0; j < n / 2; ++j) {
const int leftCell = grid[m / 2][j];
const int rightCell = grid[m / 2][n - 1 - j];
mismatchedPairs += leftCell ^ rightCell;
middleOnes += leftCell + rightCell;
}
// Handle the middle column if the number of columns is odd.
if (n % 2 == 1)
for (int i = 0; i < m / 2; ++i) {
const int topCell = grid[i][n / 2];
const int bottomCell = grid[m - 1 - i][n / 2];
mismatchedPairs += topCell ^ bottomCell;
middleOnes += topCell + bottomCell;
}
if (mismatchedPairs == 0) {
// Since there's no mismatched pairs, middleOnes % 4 must be 0 or 2.
if (middleOnes % 4 == 2)
ans += 2; // Flip two 1s to 0s.
} else {
// Flip every mismatched pair 01 to 00 or 11. It doesn't matter.
ans += mismatchedPairs;
}
// Handle the center cell if both dimensions are odd.
if (m % 2 == 1 && n % 2 == 1)
ans += grid[m / 2][n / 2];
return ans;
}
}; /* code provided by PROGIEZ */
3240. Minimum Number of Flips to Make Binary Grid Palindromic II LeetCode Solution in Java
class Solution {
public int minFlips(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
int ans = 0;
int middleOnes = 0;
int mismatchedPairs = 0;
// Handle top-left, top-right, bottom-left, bottom-right cells.
for (int i = 0; i < m / 2; ++i) {
for (int j = 0; j < n / 2; ++j) {
final int ones =
grid[i][j] + grid[i][n - 1 - j] + grid[m - 1 - i][j] + grid[m - 1 - i][n - 1 - j];
ans += Math.min(ones, 4 - ones);
}
}
// Handle the middle row if the number of m is odd.
if (m % 2 == 1)
for (int j = 0; j < n / 2; ++j) {
final int leftCell = grid[m / 2][j];
final int rightCell = grid[m / 2][n - 1 - j];
mismatchedPairs += leftCell ^ rightCell;
middleOnes += leftCell + rightCell;
}
// Handle the middle column if the number of columns is odd.
if (n % 2 == 1)
for (int i = 0; i < m / 2; ++i) {
final int topCell = grid[i][n / 2];
final int bottomCell = grid[m - 1 - i][n / 2];
mismatchedPairs += topCell ^ bottomCell;
middleOnes += topCell + bottomCell;
}
if (mismatchedPairs == 0) {
// Since there's no mismatched pairs, middleOnes % 4 must be 0 or 2.
if (middleOnes % 4 == 2)
ans += 2; // Flip two 1s to 0s.
} else {
// Flip every mismatched pair 01 to 00 or 11. It doesn't matter.
ans += mismatchedPairs;
}
// Handle the center cell if both dimensions are odd.
if (m % 2 == 1 && n % 2 == 1)
ans += grid[m / 2][n / 2];
return ans;
}
} // code provided by PROGIEZ
3240. Minimum Number of Flips to Make Binary Grid Palindromic II LeetCode Solution in Python
class Solution:
def minFlips(self, grid: list[list[int]]) -> int:
m = len(grid)
n = len(grid[0])
ans = 0
middleOnes = 0
mismatchedPairs = 0
# Handle top-left, top-right, bottom-left, bottom-right cells.
for i in range(m // 2):
for j in range(n // 2):
ones = (grid[i][j] + grid[i][n - 1 - j] +
grid[m - 1 - i][j] + grid[m - 1 - i][n - 1 - j])
ans += min(ones, 4 - ones)
# Handle the middle row if the number of m is odd.
if m % 2 == 1:
for j in range(n // 2):
leftCell = grid[m // 2][j]
rightCell = grid[m // 2][n - 1 - j]
mismatchedPairs += leftCell ^ rightCell
middleOnes += leftCell + rightCell
# Handle the middle column if the number of columns is odd.
if n % 2 == 1:
for i in range(m // 2):
topCell = grid[i][n // 2]
bottomCell = grid[m - 1 - i][n // 2]
mismatchedPairs += topCell ^ bottomCell
middleOnes += topCell + bottomCell
if mismatchedPairs == 0:
# Since there's no mismatched pairs, middleOnes % 4 must be 0 or 2.
if middleOnes % 4 == 2:
ans += 2 # Flip two 1s to 0s.
else:
# Flip every mismatched pair 01 to 00 or 11. It doesn't matter.
ans += mismatchedPairs
# Handle the center cell if both dimensions are odd.
if m % 2 == 1 and n % 2 == 1:
ans += grid[m // 2][n // 2]
return ans # code by PROGIEZ
