3240. Minimum Number of Flips to Make Binary Grid Palindromic II

Problem Description

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 1s in grid divisible by 4.

Intuition

The goal is to make all rows and columns palindromic with the minimum number of flips, ensuring the number of 1s is divisible by 4.

Consider a grid element and its mirror images across the central axes of symmetry in the grid. Each group of four such symmetric elements needs to be identical to satisfy the palindromic condition for both rows and columns. For each group of four elements, we count how many are 1s (cnt1). The minimum flips required for this group to be palindromic is the lesser of cnt1 or 4 - cnt1 (making all 1s or all 0s).

The challenge extends beyond balancing individual groups when m or n is odd.

If both m and n are even, each symmetric group can be separately optimized.
If both m and n are odd, extra consideration is needed for the center element and middle row/column to maintain divisibility by 4. Alterations in these cases might impact the total count of 1s.
For scenarios with odd m or n, the symmetric groups along the middle row or column must be checked for divisibility constraints.

Thus, understanding the symmetric properties of the grid and methodically addressing the symmetry groups allows for an optimal solution to the problem.

Learn more about Two Pointers patterns.

Solution Approach

The solution employs a systematic approach to make all rows and columns palindromic with the minimum number of flips, ensuring the number of 1s is divisible by 4. Here's a detailed walk-through:

Divide the Grid: Analyze each 2x2 group within the matrix. For a group consisting of elements grid[i][j], grid[m-i-1][j], grid[i][n-j-1], and grid[m-i-1][n-j-1], calculate the count of 1s as cnt1.
Minimize Flips: For each 2x2 group, determine the minimum flips required by computing min(cnt1, 4 - cnt1). This accounts for converting all elements in the group to either 0s or 1s to maintain a symmetric configuration.
Handle Grid Parity:
- If both dimensions are even, this approach suffices, as all groups are symmetric.
- Adjustments might be needed if m or n is odd. The middle row or column needs attention:
  - For odd m, process the middle row. Identify differing cell pairs and compute cnt1, the number of 1s aligned symmetrically.
  - If cnt1 % 4 = 0, convert differing pairs to 0s.
  - Otherwise, convert two 1s to 0s to restore divisibility, adjusting as necessary.
Special Handling of the Center: When both m and n are odd, consider the center cell separately. It should be 0 when needed to maintain the divisibility condition.
Compute Total Flips: Sum up all calculated flips, including any adjustments for symmetry or central elements.

By intelligently examining and manipulating the structure of the grid, the approach efficiently reaches a solution that meets the problem's constraints.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider a simple 3 x 3 binary matrix grid:

1 0 1
0 0 0
1 0 1

We need to make all rows and columns palindromic while ensuring the number of 1s is divisible by 4.

Divide the Grid: Start by examining the 2x2 groups. Here, given the small size, the central elements will also have direct impact due to m and n being odd.
Examine Central Symmetry:
- Center at row 1, column 1, the grid's center element, is 0. This remains unchanged since it does not affect palindrome symmetry directly in larger groups.
Middle Row and Column:
- Middle row (second row) is 0 0 0, already palindromic.
- Middle column (second column) is 0 0 0, already palindromic.
Outer Elements Formation:
- For corner elements (first and last row/column pairs), 1s are in symmetric positions already ensuring palindromic rows and columns:
  - Top row: 1 0 1 (palindromic)
  - Bottom row: 1 0 1 (palindromic)
  - Left column: 1 0 1 (palindromic)
  - Right column: 1 0 1 (palindromic)
Flipping Process:
- There are no flips needed since all rows and columns are already palindromic.
- Sum of 1s is 4, which is divisible by 4.

Thus, the minimum number of flips required to achieve the goal is 0.

This walk-through shows a scenario where the initial configuration naturally satisfies all conditions. If the grid were different, the approach of checking 2x2 symmetrical groups and making necessary flips would be employed.

Solution Implementation

1from typing import List
2
3class Solution:
4    def minFlips(self, grid: List[List[int]]) -> int:
5        m, n = len(grid), len(grid[0])  # Get dimensions of the grid
6        ans = 0  # Initialize number of flips required
7      
8        # Process the grid in 2x2 blocks
9        for i in range(m // 2):
10            for j in range(n // 2):
11                # Calculate corresponding opposite corners
12                x, y = m - i - 1, n - j - 1
13                # Count the total number of 1s in the current 2x2 block
14                cnt1 = grid[i][j] + grid[x][j] + grid[i][y] + grid[x][y]
15                # Add the minimum flips required to make the block all 0s or all 1s
16                ans += min(cnt1, 4 - cnt1)
17      
18        # If both dimensions are odd, consider the center element of the grid
19        if m % 2 and n % 2:
20            ans += grid[m // 2][n // 2]
21      
22        diff = 0  # Initialize difference counter
23        cnt1 = 0  # Counter for the ones in the middle row or column
24      
25        # If there's an extra row, evaluate its middle element symmetrically
26        if m % 2:
27            for j in range(n // 2):
28                # Check mirrored elements
29                if grid[m // 2][j] == grid[m // 2][n - j - 1]:
30                    cnt1 += grid[m // 2][j] * 2  # Add to counter if they are the same
31                else:
32                    diff += 1  # Increment difference if they are different
33      
34        # If there's an extra column, evaluate its middle element symmetrically
35        if n % 2:
36            for i in range(m // 2):
37                # Check mirrored elements
38                if grid[i][n // 2] == grid[m - i - 1][n // 2]:
39                    cnt1 += grid[i][n // 2] * 2  # Add to counter if they are the same
40                else:
41                    diff += 1  # Increment difference if they are different
42      
43        # Adjust answer based on the counter values
44        ans += diff if cnt1 % 4 == 0 or diff else 2
45      
46        return ans
47

1class Solution {
2    public int minFlips(int[][] grid) {
3        int m = grid.length;
4        int n = grid[0].length;
5        int ans = 0;
6      
7        // Traverse the top-left quadrant of the grid
8        for (int i = 0; i < m / 2; ++i) {
9            for (int j = 0; j < n / 2; ++j) {
10                int x = m - i - 1;
11                int y = n - j - 1;
12              
13                // Count the number of 1s in the current subgrid
14                int cnt1 = grid[i][j] + grid[x][j] + grid[i][y] + grid[x][y];
15              
16                // Add the minimum flips needed for the current subgrid
17                ans += Math.min(cnt1, 4 - cnt1);
18            }
19        }
20
21        // If there's a central element in an odd-length grid, increment the answer based on its value
22        if (m % 2 == 1 && n % 2 == 1) {
23            ans += grid[m / 2][n / 2];
24        }
25
26        int diff = 0;
27        int cnt1 = 0;
28
29        // Handle the middle row if the number of rows is odd
30        if (m % 2 == 1) {
31            for (int j = 0; j < n / 2; ++j) {
32                if (grid[m / 2][j] == grid[m / 2][n - j - 1]) {
33                    cnt1 += grid[m / 2][j] * 2;
34                } else {
35                    diff += 1;
36                }
37            }
38        }
39
40        // Handle the middle column if the number of columns is odd
41        if (n % 2 == 1) {
42            for (int i = 0; i < m / 2; ++i) {
43                if (grid[i][n / 2] == grid[m - i - 1][n / 2]) {
44                    cnt1 += grid[i][n / 2] * 2;
45                } else {
46                    diff += 1;
47                }
48            }
49        }
50      
51        // Adjust the answer based on the symmetry of the middle row/column
52        ans += cnt1 % 4 == 0 || diff > 0 ? diff : 2;
53      
54        return ans;
55    }
56}
57

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    int minFlips(std::vector<std::vector<int>>& grid) {
7        // Obtain the dimensions of the grid
8        int rows = grid.size();
9        int cols = grid[0].size();
10      
11        int minimumFlips = 0;
12      
13        // Iterate through each "quadrant" in the matrix
14        for (int i = 0; i < rows / 2; ++i) {
15            for (int j = 0; j < cols / 2; ++j) {
16                // Determine the symmetrical counterpart coordinates
17                int symmetricRow = rows - i - 1;
18                int symmetricCol = cols - j - 1;
19              
20                // Count the number of 1s in the four symmetric cells
21                int countOfOnes = grid[i][j] + grid[symmetricRow][j] + grid[i][symmetricCol] + grid[symmetricRow][symmetricCol];
22              
23                // Minimum flips needed to make all four cells equal
24                minimumFlips += std::min(countOfOnes, 4 - countOfOnes);
25            }
26        }
27      
28        // If grid has an odd number of rows and columns
29        if (rows % 2 == 1 && cols % 2 == 1) {
30            // Add the center element if present (only in an odd x odd grid)
31            minimumFlips += grid[rows / 2][cols / 2];
32        }
33
34        int symmetricalDiff = 0;
35        int countOnesInSymmetricalLines = 0;
36
37        // Handle the middle row if rows are odd
38        if (rows % 2 == 1) {
39            for (int j = 0; j < cols / 2; ++j) {
40                // Compare symmetrical cells in the middle row
41                if (grid[rows / 2][j] == grid[rows / 2][cols - j - 1]) {
42                    countOnesInSymmetricalLines += grid[rows / 2][j] * 2;
43                } else {
44                    symmetricalDiff += 1;
45                }
46            }
47        }
48      
49        // Handle the middle column if columns are odd
50        if (cols % 2 == 1) {
51            for (int i = 0; i < rows / 2; ++i) {
52                // Compare symmetrical cells in the middle column
53                if (grid[i][cols / 2] == grid[rows - i - 1][cols / 2]) {
54                    countOnesInSymmetricalLines += grid[i][cols / 2] * 2;
55                } else {
56                    symmetricalDiff += 1;
57                }
58            }
59        }
60      
61        // Adjust the minimum flips for the symmetrical center lines
62        minimumFlips += (countOnesInSymmetricalLines % 4 == 0 || symmetricalDiff > 0) ? symmetricalDiff : 2;
63      
64        return minimumFlips;
65    }
66};
67

1function minFlips(grid: number[][]): number {
2    const m = grid.length; // Number of rows in the grid
3    const n = grid[0].length; // Number of columns in the grid
4    let ans = 0; // Initialize the number of minimum flips needed to 0
5
6    // Iterate over each cell of the top-left quadrant of the grid
7    for (let i = 0; i < Math.floor(m / 2); i++) {
8        for (let j = 0; j < Math.floor(n / 2); j++) {
9            const x = m - i - 1; // Diagonal matching row in the bottom half
10            const y = n - j - 1; // Diagonal matching column in the right half
11            const cnt1 = grid[i][j] + grid[x][j] + grid[i][y] + grid[x][y]; // Count of 1s in the 2x2 block
12            ans += Math.min(cnt1, 4 - cnt1); // Add minimum flips needed for this 2x2 block
13        }
14    }
15
16    // If grid is odd in both dimensions, handle the center element
17    if (m % 2 === 1 && n % 2 === 1) {
18        ans += grid[Math.floor(m / 2)][Math.floor(n / 2)];
19    }
20
21    let diff = 0; // Difference counter for unmatched central elements
22    let cnt1 = 0; // Counter to accumulate similar center-line elements
23  
24    // Handle the middle row if the number of rows is odd
25    if (m % 2 === 1) {
26        for (let j = 0; j < Math.floor(n / 2); j++) {
27            if (grid[Math.floor(m / 2)][j] === grid[Math.floor(m / 2)][n - j - 1]) {
28                cnt1 += grid[Math.floor(m / 2)][j] * 2; // Double add if elements are the same
29            } else {
30                diff += 1; // Increment diff if elements do not match
31            }
32        }
33    }
34
35    // Handle the middle column if the number of columns is odd
36    if (n % 2 === 1) {
37        for (let i = 0; i < Math.floor(m / 2); i++) {
38            if (grid[i][Math.floor(n / 2)] === grid[m - i - 1][Math.floor(n / 2)]) {
39                cnt1 += grid[i][Math.floor(n / 2)] * 2; // Double add if elements are the same
40            } else {
41                diff += 1; // Increment diff if elements do not match
42            }
43        }
44    }
45
46    // Add additional flips based on unmatched center-line elements
47    ans += cnt1 % 4 === 0 || diff > 0 ? diff : 2;
48    return ans;
49}
50

Time and Space Complexity

The time complexity of the code is O(m * n), where m is the number of rows and n is the number of columns in the matrix. This is because the code iterates over approximately half of the matrix elements in a nested loop, and potentially performs an additional pass along a row or column when m or n is odd.

The space complexity is O(1), as the algorithm does not use any additional data structures whose size depends on the input size. It uses a constant amount of extra space for variables such as ans, cnt1, and diff.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which type of traversal does breadth first search do?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know