Flip Columns For Maximum Number of Equal Rows: Pattern Matching in Matrices

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

This is LeetCode 1072: Flip Columns For Maximum Number of Equal Rows, a medium problem that teaches you how to recognize hidden equivalences between rows using pattern normalization and hash maps.

Why this problem matters

At first glance, this looks like a brute force search over all possible subsets of columns to flip. With n columns, there are 2^n possible sets of flips, and for each one you would check every row. That approach is far too slow.

The real value of this problem is that it forces you to find a smarter representation. Instead of trying every combination of flips, you need to realize that certain rows are fundamentally "the same" because they would all become uniform after the same set of flips. Recognizing equivalence classes and grouping by canonical form is a pattern that shows up in anagram grouping, isomorphic strings, and many other hash map problems.

Once you see the connection between pattern normalization and grouping, the O(m * n) solution writes itself. The hard part is the insight, not the code.

The key insight

Two rows can both become all-equal after the same column flips if and only if they are identical or they are complements of each other. Think about it: if you flip a set of columns to make row A all zeros, then any row that matches A will also become all zeros. And any row that is the bitwise complement of A will become all ones.

So the question reduces to: which group of rows (where rows and their complements count as the same group) is the largest?

You can normalize each row to a canonical form by XOR-ing every element with the first element in that row. If the first element is 0, the row stays the same. If the first element is 1, the row gets flipped. This maps both a pattern and its complement to the same canonical form, because [1,1,0] XOR-ed with 1 gives [0,0,1], and [0,0,1] XOR-ed with 0 gives [0,0,1].

The solution

def maxEqualRowsAfterFlips(matrix):
    from collections import Counter

    count = Counter()
    for row in matrix:
        pattern = tuple(val ^ row[0] for val in row)
        count[pattern] += 1

    return max(count.values())

Here is what each piece does:

1. For each row, we compute its canonical pattern by XOR-ing every element with the first element (row[0]). This normalizes both [0,0,1] and [1,1,0] to the same tuple (0,0,1).
2. We use a Counter (a hash map) to count how many rows map to each canonical pattern.
3. The answer is simply the largest count. That many rows can all become uniform after the same set of column flips.

Visual walkthrough

Let's trace through the matrix [[0,0,0],[0,0,1],[1,1,0]] step by step. We normalize each row, group by pattern, and pick the largest group.

Row 0 is [0,0,0] and Row 2 is [1,1,0]. After normalization, both map to (0,0,0). That means flipping zero columns leaves Row 0 as all zeros, and flipping all columns turns Row 2 into all zeros too. Two rows can be made uniform, so the answer is 2.

Complexity analysis

This is optimal. You need to examine every cell at least once, and you need to store the patterns to count them. There is no way to avoid O(m * n) work.

Building blocks

This problem combines two reusable patterns that CodeBricks drills independently.

1. Canonical form grouping

The pattern of normalizing elements to a canonical representation and grouping by that key:

groups = defaultdict(list)
for item in items:
    key = canonicalize(item)
    groups[key].append(item)

This exact approach solves anagram grouping (sort each word), isomorphic strings (map each character to its first-occurrence index), and this problem (XOR with the first element). The canonical form collapses an equivalence class into a single key.

2. XOR-based normalization

The pattern of using XOR to toggle between a value and its complement:

normalized = tuple(val ^ row[0] for val in row)

XOR with 0 leaves a bit unchanged. XOR with 1 flips it. By XOR-ing with the first element, you always start the normalized form with 0, which means a row and its complement both map to the same result. This trick appears in problems involving bit flipping, toggle operations, and complement detection.

3. Counter for max frequency

The pattern of counting occurrences and returning the maximum:

count = Counter(patterns)
return max(count.values())

Simple frequency counting with a hash map is one of the most common building blocks. It shows up in majority element, top-K frequent, and many grouping problems.

Edge cases

Before submitting, make sure your solution handles these:

• Single row: any single row can always be made all-equal by flipping the appropriate columns. Answer is always 1.
• All identical rows: every row maps to the same pattern. Answer equals the number of rows.
• All rows are complements of one other row: for example, [[0,1],[1,0],[0,1]]. Rows 0, 2 are identical and Row 1 is the complement. All three normalize to (0,1). Answer is 3.
• Single column matrix: every row is either [0] or [1]. After normalization, all map to (0,). Answer equals the number of rows.
• No two rows share a pattern: the answer is 1, since each row can be made uniform on its own.

The solution handles all of these naturally without any special-case logic.

From understanding to recall

You have seen how normalizing rows with XOR and counting patterns with a hash map solves this problem in a single pass. The logic is compact: one loop, one Counter, one max call. But can you reproduce it under interview pressure?

The details that matter are: using row[0] as the XOR key, converting to a tuple for hashing, and remembering that complements map to the same form. These are small points that are easy to forget after a single reading. Spaced repetition turns that reading into reliable recall. You practice writing the normalization loop and the Counter logic from scratch at increasing intervals. After a few rounds, you see "maximize equal rows after flips" and the pattern grouping approach flows out automatically.

Related posts

• Set Matrix Zeroes - In-place matrix modification using row and column markers
• Score After Flipping Matrix - Greedy row and column flipping to maximize binary matrix scores
• Valid Sudoku - Hash set validation across rows, columns, and sub-boxes in a matrix

CodeBricks breaks the Flip Columns For Maximum Number of Equal Rows problem into its canonical form grouping, XOR normalization, and frequency counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern matching approach is automatic. When a matrix equivalence question shows up in your interview, you do not pause to rethink the approach. You just write it.