Domain 2MediumMEDIUM

Flip Columns For Maximum Number of Equal Rows

Normalize each row to start with a 0 using column flips, then count frequencies of canonical keys in a hash map.

Domain: medium•Updated: 2026-09-08
#normalization#hash-map#O(m*n)#worst-case-storage

Problem Breakdown

We are given an m×nm \times n binary matrix. The goal is to flip any number of columns (changing all bits in that column from 0 to 1 or vice versa) such that the maximum number of rows become uniform (all values equal). A row becomes uniform if it consists entirely of 0s or entirely of 1s after flips.

Inputs:

  • matrix: An m×nm \times n list of lists containing integers 0 and 1.

Outputs:

  • Integer: The maximum count of rows that can be made uniform simultaneously.

Constraints & Edge Cases:

  • Matrix dimensions up to 300×300300 \times 300. This allows for an algorithm with time complexity around O(mn)O(mn).
  • Values are strictly binary (0 or 1).
  • Rows must become all 0s OR all 1s. It does not matter which state they end in, as long as the row is uniform.

Intuition

Flipping a column affects every row at that specific index simultaneously. If we have two rows that are identical (e.g., [0, 1] and [0, 1]), any set of column flips applied to make one uniform will apply identically to the other. Thus, they belong to the same equivalence class.

If we have two inverse rows (e.g., [0, 1] and [1, 0]), flipping all columns that correspond to 1s in the first row effectively transforms both into a state where one is uniform or vice versa relative to each other. Specifically, if Row A becomes all 0s after flips, its inverse (Row B) will become all 1s. Both are considered “uniform”.

Key Insight: Two rows can be made uniform simultaneously if and only if they are either identical bitwise OR inverses of each other. We do not need to track which specific flip pattern is used; we just need to group compatible rows together. To simplify grouping, we normalize every row so that it always starts with a 0. If the first element is 1, we invert all bits in that row (conceptually) and use this inverted version as a canonical key for our hash map. This merges identical rows and inverse rows into the same bucket.

Approach

  1. Initialize an empty frequency dictionary (counts) to store how many times each normalized pattern appears.
  2. Iterate through each row in the matrix:
    • Check the first element of the current row (index 0).
    • If it is 0, use the tuple representation of the row directly as the key for our dictionary. This represents rows that are already “aligned” to start with a zero.
    • If it is 1, invert all bits in the row (x→1−xx \to 1-x) and use this inverted tuple as the key. For example, [1, 0] becomes (0, 1) which matches the canonical form of an identical row starting with 0.
    • Increment the count for this specific normalized key.
  3. After processing all rows, return the maximum value found in our frequency dictionary. If no keys exist (empty matrix), handle gracefully by returning 0.

Complexity Analysis

  • Time Complexity: O(m×n)O(m \times n), where mm is number of rows and nn is columns. We iterate through each cell exactly once to construct the tuple key for hashing. Hashing a tuple takes time proportional to its length (nn), so total work per row is linear in width.
  • Space Complexity: In the worst case, we store up to mm unique keys of length nn. Thus, space complexity is bounded by O(m×n)O(m \times n). Given constraints (3002=90,000300^2 = 90,000), this fits well within memory limits.

Solution

from collections import defaultdict

def maxEqualRowsAfterFlips(matrix):
    counts = defaultdict(int)
    
    for row in matrix:
        # Normalize the row so that it always starts with a 0.
        # If the first element is 1, flip all bits to create a canonical key 
        # representing this equivalence class (identical or inverse rows).
        if row[0] == 1:
            # Create inverted tuple for hashing
            counts[tuple(1 - x for x in row)] += 1
        else:
            # Use original tuple as hashable key
            counts[tuple(row)] += 1
            
    return max(counts.values()) if counts else 0

# Example usage / Test cases from problem description
if __name__ == "__main__":
    print(maxEqualRowsAfterFlips([[0,1],[1,1]])) # Output: 1
    print(maxEqualRowsAfterFlips([[0,1],[1,0]])) # Output: 2
    print(maxEqualRowsAfterFlips([[0,0,0],[0,0,1],[1,1,0]])) # Output: 2

Edge Cases Handled

  • Single Row/Column: The logic holds regardless of dimensions; a single row is always uniform after appropriate flips (count = 1).
  • All Identical Rows: All map to the same key without inversion. Count equals mm.
  • Inverse Pairs Only: E.g., [[0,1], [1,0]]. First maps to (0,1), second inverts to (0,1). Both increment same bucket. Max count = 2.
  • Empty Matrix (Hypothetical): The code checks if the dictionary is empty before calling max(), returning 0 safely, though constraints prevent this input (m,n≥1m,n \ge 1).