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

Flip Columns For Maximum Number of Equal Rows

Number: 1147

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Microsoft

Problem Description

Given an m x n binary matrix, you are allowed to flip any number of columns (i.e., change every 0 to 1 and every 1 to 0 in that column). The goal is to determine the maximum number of rows that can be made equal (all 0’s or all 1’s) after performing some flips.

Key Insights

  • Every row can be transformed into an all-0 (or all-1) row by flipping the columns where the value is 1 (or 0), but the answer is invariant if we choose one target state.
  • Two rows can be made equal if one is either identical to the other or the complement of the other.
  • By normalizing each row relative to its first column (or any fixed pivot), rows that require the same set of flips can be grouped together.
  • Use a hash map to count the frequency of each normalized row configuration.

Space and Time Complexity

Time Complexity: O(m * n), since each of the m rows (with n columns) is processed once. Space Complexity: O(m * n), for storing the normalized row patterns in the hash map.

Solution

The approach is to normalize each row so that if a row starts with 1, we flip the entire row (i.e., take its complement) to make it start with 0. This normalized row represents the pattern of flips needed to turn the row into an all-0 row. Rows with the same normalized pattern can be made all-0 simultaneously by flipping the corresponding columns. Count the frequency of each normalized pattern using a hash map, and the answer is the maximum frequency among these patterns.

Code Solutions

# Define the function to calculate the maximum number of equal rows after flips.
def maxEqualRowsAfterFlips(matrix):
    # Dictionary to map normalized row patterns to their count.
    pattern_counts = {}
    
    # Process each row in the matrix.
    for row in matrix:
        # Normalize the row so that the first element becomes 0.
        # If the first element is 1, flip the whole row by taking the complement.
        # Convert the resulting normalized row to a tuple to use as a hashable key.
        if row[0] == 1:
            normalized = tuple(1 - bit for bit in row)
        else:
            normalized = tuple(row)
        
        # Increase the count for this normalized pattern.
        pattern_counts[normalized] = pattern_counts.get(normalized, 0) + 1
    
    # The answer is the maximum frequency among all normalized patterns.
    return max(pattern_counts.values())

# Example usage:
matrix = [[0,1],[1,0]]
print(maxEqualRowsAfterFlips(matrix))  # Expected output: 2
← Back to All Questions