We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Flips to Make Binary Grid Palindromic II

Difficulty: Medium

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

Key Insights

  • A row or column can only be palindromic if it has symmetrical values around its center.
  • Flipping a single cell can impact both the row and column it belongs to.
  • The total number of 1's must be adjusted to ensure divisibility by 4.
  • Analyzing the grid in quadrants can simplify the problem of determining the number of flips required.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(1)

Solution

To solve the problem, we can use a greedy approach by examining pairs of opposite cells in the grid. For each pair, we can determine the number of flips required to make them equal, thereby contributing to the overall palindromic structure. Additionally, we must ensure that the total count of 1's in the grid is divisible by 4, which may require adjusting the number of flips accordingly.

Algorithm Steps:

  1. Iterate through each quadrant of the grid, comparing corresponding cells.
  2. Count the minimum flips required to make each pair equal.
  3. Keep track of the total number of 1's and adjust for divisibility by 4 if necessary.

Code Solutions

def minFlips(grid):
    m, n = len(grid), len(grid[0])
    flips = 0
    count_ones = 0
    
    for i in range((m + 1) // 2):
        for j in range((n + 1) // 2):
            # Identify the four corresponding cells
            cells = [grid[i][j], grid[i][n - 1 - j], grid[m - 1 - i][j], grid[m - 1 - i][n - 1 - j]]
            count_ones += sum(cells)
            # Count the number of 0s and 1s
            zeros = cells.count(0)
            ones = cells.count(1)
            flips += min(zeros, ones) + (ones % 2)  # If there's an odd count of 1's, we need one more flip
            
    # Check if the total number of 1's is divisible by 4
    if count_ones % 4 != 0:
        flips += 1  # Adjust for divisibility by 4
    
    return flips
← Back to All Questions