# 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:

```python
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

| Item | Meaning |
|---|---|
| Input | A binary matrix `grid` |
| Output | The maximum possible score after flips |
| Constraint | `1 <= rows, cols <= 20` |
| Values | Each cell is `0` or `1` |

Function shape:

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

## Examples

Example 1:

```python
grid = [
    [0, 0, 1, 1],
    [1, 0, 1, 0],
    [1, 1, 0, 0],
]
```

We can flip the first row:

```python
[
    [1, 1, 0, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 0],
]
```

Now consider columns.

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

```python
[
    [1, 1, 1, 0],
    [1, 0, 0, 0],
    [1, 1, 1, 0],
]
```

The fourth column also benefits from flipping:

```python
[
    [1, 1, 1, 1],
    [1, 0, 0, 1],
    [1, 1, 1, 1],
]
```

Now interpret each row as binary:

| Row | Binary value |
|---|---:|
| `1111` | `15` |
| `1001` | `9` |
| `1111` | `15` |

Total score:

```python
15 + 9 + 15 = 39
```

So the answer is:

```python
39
```

## First Thought: Try All Flip Combinations

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

If there are:

```python
m rows
n columns
```

then there are:

```python
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:

| Binary | Decimal |
|---|---:|
| `1000` | `8` |
| `0111` | `7` |

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 `1`s as possible.

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

## Algorithm

Let:

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

Step 1:

Ensure every row begins with `1`.

Instead of actually flipping rows, observe:

If:

```python
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:

```python
1 - grid[r][c]
```

- Otherwise, it stays:

```python
grid[r][c]
```

Step 2:

For each column:

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

The place value of column `c` is:

```python
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:

```python
2^(cols - 1)
```

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

```python
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 `1`s in that column.

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

- Keeping the column contributes:

```python
k * v
```

- Flipping the column contributes:

```python
(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

| Metric | Value | Why |
|---|---|---|
| Time | `O(rows * cols)` | We scan every cell once |
| Space | `O(1)` | Only counters and the answer are stored |

## Implementation

```python
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:

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

The variable:

```python
answer = 0
```

stores the final score.

For every column:

```python
for col in range(cols):
```

we count the effective number of `1`s.

For each row:

```python
value = grid[row][col]
```

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

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

then the bit is inverted logically.

We add the effective bit value:

```python
ones += value
```

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

```python
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:

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

For example:

| Column index | Place value |
|---|---:|
| `0` | `8` |
| `1` | `4` |
| `2` | `2` |
| `3` | `1` |

Finally, add the contribution:

```python
answer += ones * place_value
```

## Testing

```python
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:

| Test | Why |
|---|---|
| Official-style example | Checks row and column flips together |
| Single zero cell | Minimum flip case |
| Single one cell | Already optimal |
| Mixed small matrix | Checks column optimization |
| All zeros | Requires flipping rows and columns |
| All ones | Already maximum score |