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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Flips to Make Binary Grid Palindromic I

Number: 3526

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an m x n binary matrix grid, a row or a column is considered palindromic if its values read the same forward and backward. You are allowed to flip any cell (from 0 to 1 or 1 to 0). The task is to return the minimum number of flips required so that either every row becomes palindromic or every column becomes palindromic.

Key Insights

  • The operations to make all rows palindromic or all columns palindromic are independent.
  • For each individual row (or column), the minimum number of flips needed is to make every symmetric pair match. Only half of the row (or column) needs to be checked (ignoring the middle element in case of odd length).
  • The result is the minimum between the total flips required for all rows and the total flips required for all columns.

Space and Time Complexity

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

Solution

The algorithm consists of two parts.

  1. Calculate the total flips needed to make each row palindromic:
    • For each row, compare the element at position j and its symmetric counterpart at position n-1-j. If they differ, count a flip.
  2. Calculate the total flips needed to make each column palindromic:
    • For each column, compare the element at row i and its symmetric counterpart at row m-1-i. If they differ, count a flip. Finally, return the minimum of these two totals.

Key data structures used include iterators over rows and columns. The approach leverages simple arithmetic to index symmetric pairs, ensuring a linear pass over the grid without extra space.

Code Solutions

# Python solution
def minFlipsToMakePalindrome(grid):
    m = len(grid)
    n = len(grid[0])
    
    # Calculate flips needed for each row to be palindromic
    row_flips = 0
    for i in range(m):
        # Only need to check first half of the row
        for j in range(n // 2):
            # If the element and its mirror are different, one flip is needed
            if grid[i][j] != grid[i][n - 1 - j]:
                row_flips += 1

    # Calculate flips needed for each column to be palindromic
    col_flips = 0
    for j in range(n):
        # Only need to check first half of the column
        for i in range(m // 2):
            # If the element and its mirror are different, one flip is needed
            if grid[i][j] != grid[m - 1 - i][j]:
                col_flips += 1

    # Return the minimum flips between fixing rows or fixing columns
    return min(row_flips, col_flips)

# Example usage:
grid1 = [[1,0,0],[0,0,0],[0,0,1]]
print(minFlipsToMakePalindrome(grid1))  # Output: 2
← Back to All Questions