LeetCode 1072 - Flip Columns For Maximum Number of Equal Rows

The problem gives us an m x n binary matrix, where every element is either 0 or 1. We are allowed to choose any set of columns and flip them. Flipping a column means changing every 0 in that column to 1, and every 1 to 0.

leetcodemediumarrayhash-tablematrix

LeetCode Problem 1072

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Matrix

Solution

LeetCode 1072 - Flip Columns For Maximum Number of Equal Rows

Problem Understanding

The problem gives us an m x n binary matrix, where every element is either 0 or 1. We are allowed to choose any set of columns and flip them. Flipping a column means changing every 0 in that column to 1, and every 1 to 0.

Our goal is to maximize the number of rows that become "equal rows" after performing these flips. A row is considered valid if all values in that row are identical. In other words, after the flips, every value in that row must be either all 0s or all 1s.

The important detail is that flips are applied globally to entire columns, not individually per row. If we flip column j, that affects every row at position j.

For example, consider the rows:

[0,1]
[1,0]

If we flip the first column, they become:

[1,1]
[0,0]

Now both rows contain identical values within themselves, so both rows count.

The constraints tell us that both dimensions can be as large as 300. That means the matrix can contain up to 90,000 cells. This is small enough for O(m * n) or O(m * n log m) solutions, but trying all possible column flip combinations would be impossible because there are 2^n possible flip configurations.

Several edge cases are important:

  • Rows may already contain all equal values without any flips.
  • Some rows may be exact opposites of each other, and these rows can become equal simultaneously after appropriate flips.
  • There may only be one row or one column.
  • Multiple identical rows should all count together.
  • A naive approach might incorrectly treat only identical rows as compatible, but complementary rows are also compatible.

The key observation is understanding which rows can become uniform under the same set of column flips.

Approaches

Brute Force Approach

A straightforward approach is to try every possible combination of column flips.

Since there are n columns, each column can either be flipped or not flipped. That creates 2^n possible configurations. For each configuration:

  1. Apply the flips.
  2. Check every row.
  3. Count how many rows become all 0s or all 1s.
  4. Track the maximum.

This approach is correct because it exhaustively checks every valid flip pattern. However, it becomes infeasible very quickly. With n = 300, the number of configurations is astronomically large.

Even for relatively small values like n = 30, 2^30 is already over one billion possibilities.

Optimal Observation

The key insight is that two rows can become uniform together if and only if they are either:

  • Exactly identical
  • Exact complements of each other

Why?

Suppose we decide which columns to flip based on one row.

If a row starts as:

[0,1,0,1]

we could flip columns 1 and 3 to make it:

[0,0,0,0]

Now consider another row:

[1,0,1,0]

Applying the exact same flips produces:

[1,1,1,1]

So complementary rows become uniform together.

This means we can normalize every row into a canonical representation. One common technique is:

  • If the first element is 0, keep the row as is.
  • If the first element is 1, invert the entire row.

Rows that can become uniform together will share the same normalized form.

We can then count frequencies of normalized patterns using a hash map.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * m * n) O(1) Tries every possible column flip combination
Optimal O(m * n) O(m * n) Uses row normalization and hash counting

Algorithm Walkthrough

  1. Create a hash map to count normalized row patterns.
  2. Iterate through every row in the matrix.
  3. For each row, determine whether its first element is 0 or 1.
  4. If the first element is 0, keep the row unchanged because it already represents the canonical form.
  5. If the first element is 1, invert every value in the row. This transforms complementary rows into the same representation.
  6. Convert the normalized row into a tuple in Python, or a string key in Go, so it can be used as a hash map key.
  7. Increment the frequency count for this normalized pattern.
  8. Track the maximum frequency seen so far.
  9. After processing all rows, return the maximum frequency.

Why it works

The algorithm works because column flips are global operations. Any row can be transformed into all 0s by flipping exactly the columns where that row contains 1s.

If another row is identical, the same flips also produce all 0s.

If another row is the complement, the same flips produce all 1s.

Therefore, identical rows and complementary rows belong to the same equivalence class. Normalization guarantees that all rows in the same class map to the same key, allowing us to count the largest compatible group.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        pattern_count = defaultdict(int)
        max_rows = 0

        for row in matrix:
            if row[0] == 0:
                normalized = tuple(row)
            else:
                normalized = tuple(1 - value for value in row)

            pattern_count[normalized] += 1
            max_rows = max(max_rows, pattern_count[normalized])

        return max_rows

The implementation begins by creating a hash map called pattern_count. This stores how many times each normalized row pattern appears.

For every row, we check the first value. If it is 0, we leave the row unchanged. If it is 1, we invert every bit in the row.

This normalization step guarantees that complementary rows produce identical normalized patterns.

The normalized row is converted into a tuple because lists cannot be used as dictionary keys in Python.

We then increment the count for that pattern and update the running maximum.

Finally, the maximum frequency is returned because it represents the largest group of rows that can simultaneously become uniform after some column flips.

Go Solution

func maxEqualRowsAfterFlips(matrix [][]int) int {
	patternCount := make(map[string]int)
	maxRows := 0

	for _, row := range matrix {
		pattern := make([]byte, len(row))

		if row[0] == 0 {
			for i, value := range row {
				pattern[i] = byte(value + '0')
			}
		} else {
			for i, value := range row {
				pattern[i] = byte((1 - value) + '0')
			}
		}

		key := string(pattern)

		patternCount[key]++

		if patternCount[key] > maxRows {
			maxRows = patternCount[key]
		}
	}

	return maxRows
}

The Go solution follows the same logic as the Python implementation.

Since slices cannot be used as map keys in Go, we convert the normalized row into a string representation. A byte slice is used for efficient construction of the string key.

The normalization process is identical:

  • Rows starting with 0 remain unchanged.
  • Rows starting with 1 are inverted.

The map tracks frequencies, and the maximum frequency is returned.

Go does not require special handling for integer overflow here because all counts remain well within standard integer limits.

Worked Examples

Example 1

Input:
matrix = [[0,1],[1,1]]

Process each row.

Row First Element Normalized Form Count Map
[0,1] 0 (0,1) {(0,1): 1}
[1,1] 1 (0,0) {(0,1): 1, (0,0): 1}

The largest frequency is 1.

Output:

1

Example 2

Input:
matrix = [[0,1],[1,0]]

Process rows.

Row First Element Normalized Form Count Map
[0,1] 0 (0,1) {(0,1): 1}
[1,0] 1 (0,1) {(0,1): 2}

Both rows normalize to the same pattern.

Output:

2

Example 3

Input:
matrix = [[0,0,0],[0,0,1],[1,1,0]]

Process rows.

Row First Element Normalized Form Count Map
[0,0,0] 0 (0,0,0) {(0,0,0): 1}
[0,0,1] 0 (0,0,1) {(0,0,0): 1, (0,0,1): 1}
[1,1,0] 1 (0,0,1) {(0,0,0): 1, (0,0,1): 2}

The largest frequency is 2.

Output:

2

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Every cell is processed exactly once
Space O(m * n) Hash map may store up to m normalized rows

The algorithm visits every row and every column exactly once during normalization. Hash map operations are average-case O(1).

The space complexity comes from storing normalized row patterns. In the worst case, every row is unique, requiring storage proportional to the total matrix size.

Test Cases

from typing import List

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        from collections import defaultdict

        pattern_count = defaultdict(int)
        max_rows = 0

        for row in matrix:
            if row[0] == 0:
                normalized = tuple(row)
            else:
                normalized = tuple(1 - value for value in row)

            pattern_count[normalized] += 1
            max_rows = max(max_rows, pattern_count[normalized])

        return max_rows

solution = Solution()

assert solution.maxEqualRowsAfterFlips([[0,1],[1,1]]) == 1
# Basic example where only one row can be uniform

assert solution.maxEqualRowsAfterFlips([[0,1],[1,0]]) == 2
# Complementary rows become uniform together

assert solution.maxEqualRowsAfterFlips([[0,0,0],[0,0,1],[1,1,0]]) == 2
# Mixed patterns with complements

assert solution.maxEqualRowsAfterFlips([[0]]) == 1
# Single row, single column

assert solution.maxEqualRowsAfterFlips([[1]]) == 1
# Single value already uniform

assert solution.maxEqualRowsAfterFlips([[0,0],[0,0],[0,0]]) == 3
# All rows identical

assert solution.maxEqualRowsAfterFlips([[1,1],[0,0],[1,1]]) == 3
# Identical and complementary rows combine

assert solution.maxEqualRowsAfterFlips([[0,1,0],[1,0,1],[0,1,0]]) == 3
# Multiple equivalent normalized rows

assert solution.maxEqualRowsAfterFlips([[0,1],[1,1],[1,0],[0,0]]) == 2
# Multiple groups with same maximum size

assert solution.maxEqualRowsAfterFlips([[0,1,1,0]]) == 1
# Single row always counts

assert solution.maxEqualRowsAfterFlips([
    [0,1,0,1],
    [1,0,1,0],
    [0,1,0,1],
    [1,0,1,0]
]) == 4
# Large complementary group

Test Case Summary

Test Why
[[0,1],[1,1]] Validates simple non-matching rows
[[0,1],[1,0]] Validates complementary row matching
[[0,0,0],[0,0,1],[1,1,0]] Validates mixed groups
[[0]] Tests smallest matrix
[[1]] Tests single value normalization
[[0,0],[0,0],[0,0]] Tests identical rows
[[1,1],[0,0],[1,1]] Tests complement normalization
[[0,1,0],[1,0,1],[0,1,0]] Tests repeated equivalent patterns
[[0,1],[1,1],[1,0],[0,0]] Tests multiple competing groups
[[0,1,1,0]] Tests single-row behavior
Large complementary group Tests scaling and grouping correctness

Edge Cases

One important edge case occurs when the matrix contains only one row. Regardless of the row contents, we can always make that row uniform by flipping the appropriate columns. The implementation handles this naturally because the normalized pattern count becomes 1, and the maximum frequency returned is also 1.

Another important case is when rows are complements of each other rather than identical. A naive implementation might fail to group these rows together. For example, [0,1,0] and [1,0,1] should belong to the same group because the same flips can make one all 0s and the other all 1s. The normalization step correctly converts both into the same canonical form.

A third edge case involves matrices where all rows are already identical. In this situation, no flips are necessary, and the answer should equal the number of rows. Since all rows normalize to the same pattern, the hash map correctly counts every occurrence.

Another subtle edge case occurs when there are multiple groups of equal size. The algorithm does not depend on identifying a unique best group. Instead, it continuously tracks the maximum frequency seen so far, ensuring the correct answer is returned even when several groups tie for the maximum.