LeetCode 861: Score After Flipping Matrix

Problem Restatement

We are given a binary matrix grid.

We may perform any number of operations.

Each operation can:

1. Flip one row
2. Flip one column

Flipping means changing:

0 -> 1
1 -> 0

After all operations, every row is interpreted as a binary number.

The total score is the sum of those binary numbers.

We need to return the largest possible score.

Input and Output

Function shape:

class Solution:
    def matrixScore(self, grid: list[list[int]]) -> int:
        ...

Examples

Example 1:

grid = [
    [0, 0, 1, 1],
    [1, 0, 1, 0],
    [1, 1, 0, 0],
]

We can flip the first row:

[
    [1, 1, 0, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 0],
]

Now consider columns.

The third column has more 0s than 1s, so flip it:

[
    [1, 1, 1, 0],
    [1, 0, 0, 0],
    [1, 1, 1, 0],
]

The fourth column also benefits from flipping:

[
    [1, 1, 1, 1],
    [1, 0, 0, 1],
    [1, 1, 1, 1],
]

Now interpret each row as binary:

Total score:

15 + 9 + 15 = 39

So the answer is:

39

First Thought: Try All Flip Combinations

A direct approach is to try all possible row and column flips.

If there are:

m rows
n columns

then there are:

2^m * 2^n

possible flip combinations.

This becomes far too large even for moderate matrix sizes.

We need to use the structure of binary numbers.

Key Insight

The leftmost bit in a binary number has the largest value.

For example:

So every row should start with 1.

If a row starts with 0, flipping that row always increases the value of that row.

Therefore:

1. First, make every first-column value equal to 1.
2. Then optimize the remaining columns independently.

After fixing the first column, each remaining column contributes independently to the total score.

For any column, we want as many 1s as possible.

If a column has more 0s than 1s, flipping that column increases the total score.

Algorithm

Let:

rows = len(grid)
cols = len(grid[0])

Step 1:

Ensure every row begins with 1.

Instead of actually flipping rows, observe:

If:

grid[r][0] == 0

then that row behaves as if every bit were flipped.

So for column c:

• If the row was flipped, the effective value becomes:

1 - grid[r][c]

• Otherwise, it stays:

grid[r][c]

Step 2:

For each column:

1. Count how many effective 1s it contains.
2. Choose the larger of:
   1. Number of 1s
   2. Number of 0s after flipping
3. Multiply by the binary place value.

The place value of column c is:

1 << (cols - 1 - c)

Add all contributions to the answer.

Correctness

Consider any row whose first bit is 0.

Flipping that row changes the first bit to 1. Since the first bit has value:

2^(cols - 1)

its contribution is larger than the combined contribution of all later bits:

2^(cols - 2) + ... + 1

Therefore, flipping such a row always increases the row value. So every optimal solution must make all first-column bits equal to 1.

After fixing the first column, each remaining column contributes independently to the final score. Flipping one column affects only the count of 1s in that column.

For a column with place value v, if it contains k ones and rows - k zeros, then:

• Keeping the column contributes:

k * v

• Flipping the column contributes:

(rows - k) * v

Choosing the larger value maximizes the contribution of that column.

Since every column is optimized independently after the first-column condition is enforced, the algorithm produces the maximum possible total score.

Complexity

Implementation

class Solution:
    def matrixScore(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        answer = 0

        for col in range(cols):
            ones = 0

            for row in range(rows):
                value = grid[row][col]

                if grid[row][0] == 0:
                    value = 1 - value

                ones += value

            ones = max(ones, rows - ones)

            place_value = 1 << (cols - 1 - col)

            answer += ones * place_value

        return answer

Code Explanation

We first compute the matrix dimensions:

rows = len(grid)
cols = len(grid[0])

The variable:

answer = 0

stores the final score.

For every column:

for col in range(cols):

we count the effective number of 1s.

For each row:

value = grid[row][col]

If the row would be flipped because its first bit is 0:

if grid[row][0] == 0:
    value = 1 - value

then the bit is inverted logically.

We add the effective bit value:

ones += value

After counting the column, we decide whether flipping the column helps:

ones = max(ones, rows - ones)

This chooses the larger count between keeping the column and flipping it.

The binary place value of the column is:

place_value = 1 << (cols - 1 - col)

For example:

Finally, add the contribution:

answer += ones * place_value

Testing

def test_matrix_score():
    s = Solution()

    assert s.matrixScore([
        [0, 0, 1, 1],
        [1, 0, 1, 0],
        [1, 1, 0, 0],
    ]) == 39

    assert s.matrixScore([
        [0],
    ]) == 1

    assert s.matrixScore([
        [1],
    ]) == 1

    assert s.matrixScore([
        [0, 1],
        [1, 1],
    ]) == 5

    assert s.matrixScore([
        [0, 0],
        [0, 0],
    ]) == 6

    assert s.matrixScore([
        [1, 1, 1],
        [1, 1, 1],
    ]) == 14

    print("all tests passed")

test_matrix_score()

Test meaning: