LeetCode 1072: Flip Columns For Maximum Number of Equal Rows

Problem Restatement

We are given an m x n binary matrix.

In one operation, we choose any column and flip all values in it (0 → 1, 1 → 0).

We want to maximize the number of rows that have all the same value (all-0 or all-1) after any number of column flips.

The official constraints state that 1 <= m, n <= 300.

Input and Output

Function shape:

def maxEqualRowsAfterFlips(matrix: list[list[int]]) -> int:
    ...

Examples

Example 1:

matrix = [[0,1],[1,1]]

Flip column 0: [[1,1],[0,1]]. Row 0 is [1,1]. One all-equal row.

Answer:

1

Example 2:

matrix = [[0,1],[1,0]]

No flips: row 0 = [0,1], row 1 = [1,0]. Flip column 0: [[1,1],[0,0]]. Both rows all-equal.

Answer:

2

Key Insight

Two rows can be made all-equal simultaneously if and only if they are identical or exact complements (one is the bitwise NOT of the other).

Normalize each row to its canonical form: if the row starts with 1, flip it. Then count the most common pattern.

Algorithm

1. For each row, compute a canonical key:
   • If row[0] == 1, flip all bits.
   • Otherwise keep as is.
2. Count occurrences of each pattern.
3. Return the maximum count.

Correctness

Two rows can be simultaneously made all-0 or all-1 if and only if they are identical or complementary. Normalizing (always starting with 0) groups identical and complementary rows together.

Edge Cases

• Duplicates usually matter; store counts when a set would lose necessary multiplicity.
• Update the frequency structure in the same order the invariant assumes.
• Check empty or one-element inputs if the problem allows them.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from collections import Counter

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: list[list[int]]) -> int:
        def key(row):
            if row[0] == 1:
                return tuple(1 - x for x in row)
            return tuple(row)

        return max(Counter(key(row) for row in matrix).values())

Testing

def run_tests():
    s = Solution()

    assert s.maxEqualRowsAfterFlips([[0,1],[1,1]]) == 1
    assert s.maxEqualRowsAfterFlips([[0,1],[1,0]]) == 2
    assert s.maxEqualRowsAfterFlips([[0,0,0],[0,0,1],[1,1,0]]) == 2

    print("all tests passed")

run_tests()