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

Flip Columns For Maximum Number of Equal Rows

Difficulty: Medium

Problem Description

You are given an m x n binary matrix matrix. You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from 0 to 1 or vice versa). Return the maximum number of rows that have all values equal after some number of flips.

Key Insights

  • Flipping a column can help in achieving equal rows.
  • Each row can be represented as a binary string or tuple.
  • To maximize the number of equal rows, we can normalize rows by flipping columns to match a reference row.
  • Using a hashmap (or dictionary), we can count occurrences of normalized rows.

Space and Time Complexity

Time Complexity: O(m * n) - where m is the number of rows and n is the number of columns, as we iterate through each row and column. Space Complexity: O(m) - for storing the normalized rows in a hashmap.

Solution

To solve this problem, we can use a hashmap to count how many rows can be made equal by flipping certain columns. For each row, we can determine a "normalized" version of that row based on the first element. This normalized version will represent how the row would look after potentially flipping columns. By counting the occurrences of these normalized rows, we can find the maximum count, which represents the maximum number of equal rows.

Code Solutions

def maxEqualRowsAfterFlips(matrix):
    from collections import defaultdict
    
    row_count = defaultdict(int)
    
    for row in matrix:
        # Normalize the row based on the first element
        normalized_row = tuple((col ^ row[0]) for col in row)
        row_count[normalized_row] += 1
    
    # The maximum number of equal rows
    return max(row_count.values())
← Back to All Questions