Score After Flipping Matrix: Greedy Bit Maximization

You are given an m x n binary matrix (every value is 0 or 1). You can flip any row (toggle every bit in that row) or any column (toggle every bit in that column) as many times as you want, in any order. Each row is then interpreted as a binary number, and your goal is to maximize the total score (the sum of all rows read as binary).

This is LeetCode 861: Score After Flipping Matrix, a medium problem that teaches you how to combine greedy reasoning with binary number properties. The trick is recognizing which bits matter most and handling them in the right order.

Why this problem matters

This problem sits at the intersection of three important patterns: greedy algorithms, matrix manipulation, and bit-level thinking. You need to realize that not all columns are created equal. The leftmost column carries the highest place value (2^(n-1)), so a single 1 in column 0 is worth more than having 1s in every other column combined.

That insight drives the entire greedy strategy. Once you see that the most significant bit dominates, you know exactly what to do: make sure every row starts with 1, then maximize 1s in every remaining column. The order of operations matters, and the greedy approach gives you the optimal result without trying every possible combination of flips.

This kind of "value-weighted greedy" thinking shows up in many problems. Whenever the contribution of an element depends on its position, and you can rearrange or toggle elements independently, there is likely a greedy solution lurking.

The brute force approach

A brute force solution would enumerate all possible combinations of row and column flips. With m rows and n columns, there are 2^m possible row-flip combinations and 2^n possible column-flip combinations, giving 2^(m+n) total states to check.

def matrixScore_brute(grid):
    m, n = len(grid), len(grid[0])
    best = 0
    for row_mask in range(1 << m):
        for col_mask in range(1 << n):
            score = 0
            for i in range(m):
                row_val = 0
                for j in range(n):
                    bit = grid[i][j]
                    if row_mask & (1 << i):
                        bit ^= 1
                    if col_mask & (1 << j):
                        bit ^= 1
                    row_val = row_val * 2 + bit
                score += row_val
            best = max(best, score)
    return best

This runs in O(2^(m+n) * m * n) time, which is far too slow for any reasonable input size. Even a 10x10 matrix would require checking over a million combinations. We need a smarter approach.

The key insight: MSB dominates everything

The most significant bit (column 0) of each row contributes 2^(n-1) to that row's value. All the remaining bits combined contribute at most 2^(n-1) - 1. This means a single 1 in the leftmost column is worth more than having 1s in every other position.

This leads to a two-phase greedy strategy:

1. Phase 1: Fix the rows. For each row, if the first element is 0, flip the entire row. This guarantees every row starts with 1, maximizing the most valuable bit position. You never want a 0 in the MSB, because the value you gain from setting it to 1 always outweighs anything you might lose in other columns.

2. Phase 2: Fix the columns. For each remaining column (from column 1 onward), count how many 1s it contains. If fewer than half the rows have a 1 in that column, flip the column. This maximizes the number of 1s in each column independently.

The beauty of this approach is that the two phases do not interfere with each other. Flipping a column does not change which value is in column 0 (since we already ensured all column-0 values are 1, flipping column 0 would make them all 0, which is always worse). And within each non-MSB column, we simply want as many 1s as possible.

Walking through it step by step

Let's trace through grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]. We first ensure every row starts with 1, then we optimize each column from left to right.

After fixing rows and optimizing columns, the total score increased from 25 to 39. Every row starts with 1 (the MSB), and each remaining column has as many 1s as possible.

The greedy solution

def matrixScore(grid):
    m, n = len(grid), len(grid[0])

    for i in range(m):
        if grid[i][0] == 0:
            for j in range(n):
                grid[i][j] ^= 1

    for j in range(1, n):
        ones = sum(grid[i][j] for i in range(m))
        if ones < m - ones:
            for i in range(m):
                grid[i][j] ^= 1

    return sum(
        sum(grid[i][j] << (n - 1 - j) for j in range(n))
        for i in range(m)
    )

1. The first loop iterates over each row. If grid[i][0] is 0, the row starts with the wrong bit, so we flip every element in that row using XOR with 1.
2. The second loop processes columns 1 through n-1. For each column, we count the number of 1s. If there are more 0s than 1s (ones < m - ones), flipping the column increases the total score, so we flip it.
3. The final expression computes the total score by reading each row as a binary number. grid[i][j] << (n - 1 - j) shifts each bit to its correct place value.

Complexity analysis

This is optimal. You must examine every cell at least once to determine whether to flip, so O(m * n) is the lower bound. And O(1) space means no auxiliary storage beyond a few counter variables.

Building blocks

This problem is built on 3 reusable patterns that CodeBricks drills independently.

1. Greedy column/row optimization

The pattern of processing a matrix one dimension at a time, making the locally optimal choice at each step:

for i in range(rows):
    if should_flip_row(i):
        flip_row(i)

for j in range(cols):
    if should_flip_col(j):
        flip_col(j)

This "fix rows first, then fix columns" decomposition works whenever row flips and column flips affect independent aspects of the objective. You will see similar two-phase strategies in problems like Set Matrix Zeroes and Game of Life, where you separate the row-level and column-level logic.

2. Bit-value positional reasoning

The pattern of recognizing that position determines value in binary representations:

value = 0
for j in range(n):
    value += bit[j] * (1 << (n - 1 - j))

Understanding that 2^k is greater than the sum of all smaller powers (2^0 + 2^1 + ... + 2^(k-1) = 2^k - 1) is the foundation of many bit manipulation problems. This insight tells you to prioritize higher-order bits above everything else.

3. Majority-count column flipping

The pattern of counting occurrences in a column and flipping when the minority value is more desirable:

for j in range(cols):
    count = sum(grid[i][j] for i in range(rows))
    if count < rows - count:
        for i in range(rows):
            grid[i][j] ^= 1

This "count and flip" logic appears whenever you want to maximize (or minimize) the total of a column-wise metric. The threshold is always half the number of rows.

Edge cases

Before submitting, make sure your solution handles these:

• Single cell [[0]]: flip the row to get [[1]], score = 1. A single 0 should always be flipped.
• All zeros [[0,0],[0,0]]: flip both rows to get [[1,1],[1,1]], score = 6. Every row and column benefits from flipping.
• Already optimal [[1,1],[1,1]]: no flips needed, score = 6. The algorithm should not flip anything when the matrix is already maximized.
• Single column [[0],[1],[0]]: flip rows 0 and 2 to get [[1],[1],[1]], score = 3. Column optimization is skipped since there is only one column.

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

Common mistakes

1. Forgetting to fix rows before columns. If you optimize columns first without ensuring all MSBs are 1, you might set column 0 to majority 1s but leave some rows with a 0 in the MSB. Fixing those rows later would undo your column work. Always handle rows first.

2. Flipping column 0 during the column phase. After fixing rows, every cell in column 0 is 1. Flipping column 0 would set them all to 0, which is always worse. Start the column loop at j=1, not j=0.

3. Using > instead of < for the column flip condition. You want to flip when the number of 1s is less than the number of 0s. Using the wrong comparison means you flip columns that are already optimal and skip ones that need fixing.

From understanding to recall

You have seen how the two-phase greedy strategy works: fix row MSBs, then maximize 1s in each column. The logic is clean and the code is short. But can you reproduce it under interview pressure without looking at it?

The critical details are: XOR to flip bits, starting the column loop at index 1 (not 0), and the ones < m - ones threshold for deciding whether to flip. These are small points that are easy to forget if you have only read about them once. Under time pressure, getting even one of them wrong means a failing submission.

Spaced repetition turns reading comprehension into reliable recall. You practice writing the row-fix loop and the column-optimization loop from scratch at increasing intervals. After a few rounds, the two-phase structure and the bit manipulation details are automatic. You see "maximize binary matrix score" and the code flows out without hesitation. The greedy column optimization pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems.

Related posts

• Flipping an Image - Row reversal and bit flipping in a binary matrix using XOR
• Set Matrix Zeroes - In-place matrix modification with row and column markers
• Game of Life - Simultaneous cell updates in a matrix using state encoding

CodeBricks breaks the Score After Flipping Matrix problem into its greedy row-fixing, majority-count column flipping, and bit-value positional reasoning building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the two-phase strategy is automatic. When a greedy matrix optimization question shows up in your interview, you do not pause to rethink the approach. You just write it.