Introduction

Matrix flipping problems appear frequently in algorithm interviews because they combine greedy reasoning and bitwise intuition. A common version asks for the maximum matrix score when you may flip any column, optionally after normalizing rows. The right approach avoids brute force and runs in linear time over matrix cells.

Problem Setup

Given a binary matrix, you may flip columns. In many formulations, row flips are also allowed and score is computed by reading each row as a binary number. The goal is to maximize total score.

Key greedy insight for score-based variant:

• the leftmost column has highest binary weight
• ensure each row starts with 1 by flipping rows if needed
• for each remaining column, choose flipped or unflipped state that yields more 1 values

This avoids trying all combinations.

Efficient Greedy Algorithm

Assume matrix has m rows and n columns.

1. Treat any row starting with 0 as logically flipped.
2. For each column j, count effective ones under that row-normalization.
3. Ones for column j should be max(count, m - count).
4. Add contribution with binary weight 2^(n - 1 - j).

Python implementation:

1from typing import List
2
3
4def matrix_score(grid: List[List[int]]) -> int:
5    if not grid or not grid[0]:
6        return 0
7
8    m, n = len(grid), len(grid[0])
9    total = 0
10
11    for col in range(n):
12        ones = 0
13        for row in range(m):
14            bit = grid[row][col]
15            # If first bit is 0, this row is effectively flipped
16            if grid[row][0] == 0:
17                bit ^= 1
18            ones += bit
19
20        best_ones = max(ones, m - ones)
21        weight = 1 << (n - 1 - col)
22        total += best_ones * weight
23
24    return total
25
26
27if __name__ == "__main__":
28    mat = [
29        [0, 0, 1, 1],
30        [1, 0, 1, 0],
31        [1, 1, 0, 0],
32    ]
33    print(matrix_score(mat))  # 39

Complexity is O(m*n) time and O(1) extra space.

Why the Greedy Choice Is Correct

After row normalization, each row has a leading 1. Any solution that leaves a leading 0 can be improved by flipping that row, because the first column weight dominates all lower bits combined.

Once first column is fixed, each remaining column is independent for score contribution. Flipping one column does not affect another column’s count of ones. So the best choice is local: maximize ones in each column individually.

That structure is what makes greedy optimal here.

Brute Force Contrast

Brute force over n columns tries 2^n combinations, which explodes quickly. With row flips included, state space can be even larger if implemented naively.

For m=100 and n=100, brute force is impossible. The greedy method still runs comfortably in a few milliseconds in Python for typical interview constraints.

Variant: Max Equal Rows After Column Flips

Another common variant asks for maximum number of equal rows after flipping columns. That is solved by normalizing each row against its first bit and counting identical normalized patterns.

1from collections import Counter
2from typing import List
3
4
5def max_equal_rows_after_flips(matrix: List[List[int]]) -> int:
6    counter = Counter()
7    for row in matrix:
8        first = row[0]
9        key = tuple(bit ^ first for bit in row)
10        counter[key] += 1
11    return max(counter.values(), default=0)
12
13
14if __name__ == "__main__":
15    mat = [[0, 1], [1, 0], [1, 1]]
16    print(max_equal_rows_after_flips(mat))  # 2

Do not confuse this variant with score maximization. The objective function changes, so algorithm details differ.

Testing Strategy

Use small deterministic tests first:

• single row
• single column
• all zeros
• all ones
• mixed random matrix

Then cross-check against brute force for tiny sizes to validate implementation correctness.

1def brute_score(grid):
2    from itertools import product
3    m, n = len(grid), len(grid[0])
4    best = 0
5    for row_mask in product([0, 1], repeat=m):
6        for col_mask in product([0, 1], repeat=n):
7            val = 0
8            for r in range(m):
9                row_val = 0
10                for c in range(n):
11                    bit = grid[r][c] ^ row_mask[r] ^ col_mask[c]
12                    row_val = (row_val << 1) | bit
13                val += row_val
14            best = max(best, val)
15    return best

Comparing greedy and brute on small random inputs is an effective guard against subtle logic mistakes.

Common Pitfalls

• Using brute force even when constraints require near-linear solutions.
• Forgetting that first-column weight dominates lower bits in score variant.
• Mutating matrix unnecessarily when logical flip interpretation is enough.
• Mixing up score-maximization and max-equal-rows variants.
• Incorrect bit weighting when summing column contributions.

Summary

• Flipping-columns matrix score problems are solved efficiently with greedy reasoning.
• Normalize rows conceptually so leading bits are maximized first.
• Then optimize each remaining column independently by majority ones.
• Time complexity is linear in number of matrix cells.
• Distinguish objective variants clearly before choosing an algorithm.