# Score After Flipping Matrix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/score-after-flipping-matrix)
Canonical: https://scaleengineer.com/dsa/problems/score-after-flipping-matrix
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Data structures:** Array, Matrix
**Companies:** [IIT Bombay](https://scaleengineer.com/companies/iit-bombay)
---
## Problem
You are given an `m x n` binary matrix `grid`.

A **move** consists of choosing any row or column and toggling each value in that row or column (i.e., changing all `0`'s to `1`'s, and all `1`'s to `0`'s).

Every row of the matrix is interpreted as a binary number, and the **score** of the matrix is the sum of these numbers.

Return _the highest possible **score** after making any number of **moves** (including zero moves)_.

**Example 1:**

![](https://assets.glich.co/dsa/score-after-flipping-matrix/image0.jpg) 

**Input:** grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
**Output:** 39
**Explanation:** 0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

**Example 2:**

**Input:** grid = [[0]]
**Output:** 1

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 20`
* `grid[i][j]` is either `0` or `1`.

# Approaches
## Brute Force over Row Combinations
This approach explores every possible combination of row toggles. Since toggling a row twice is the same as not toggling it at all, for each of the `m` rows, we have two choices: either toggle it or not. This gives `2^m` possible configurations of the matrix based on row toggles. For each of these configurations, we can then determine the optimal column toggles to maximize the score.
**Time:** O(2^m * m * n). We iterate `2^m` times for each row combination. Inside the loop, we iterate through each cell of the matrix (`m*n`) to calculate the score for that combination. · **Space:** O(1) extra space. The calculation is done on the fly without creating a temporary grid.
**Pros:** It is guaranteed to find the optimal solution by exhaustively checking all row-flip possibilities.; The logic is a direct, albeit inefficient, interpretation of the problem's move set.
**Cons:** The exponential time complexity with respect to the number of rows (`m`) makes it too slow for larger values of `m`.; It is significantly less efficient than the greedy approach.
### Explanation
The core idea is to iterate through all `2^m` possibilities for flipping the rows. We can use a bitmask from `0` to `2^m - 1` to represent which rows to flip. If the `i`-th bit is set in the mask, we consider row `i` as flipped.

For each of the `2^m` row-flipped states:
1.  We determine the best possible score. With the rows fixed, the decision to flip each column is independent.
2.  For each column, we count the number of `1`s. If flipping the column (changing `1`s to `0`s and vice-versa) results in more `1`s, we do it. This means we choose the configuration with more `1`s for each column.
3.  The score for the current row-flip combination is calculated by summing the contributions of each column, where each column is optimally configured.
4.  We keep track of the maximum score found across all `2^m` configurations. This exhaustive search over row combinations guarantees finding the optimal solution, as any final configuration can be achieved by some set of row and column flips.

Here is the implementation in Java:
```java
class Solution {
    public int matrixScore(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int maxScore = 0;

        // Iterate through all 2^m row toggle combinations using a bitmask
        for (int i = 0; i < (1 << m); i++) {
            int currentScore = 0;
            
            // For each column, calculate its contribution to the score
            for (int c = 0; c < n; c++) {
                int onesInCol = 0;
                // Count the number of 1s in the current column after row toggles
                for (int r = 0; r < m; r++) {
                    // Check if row 'r' should be toggled
                    boolean rowToggled = (i & (1 << r)) != 0;
                    int currentValue = grid[r][c];
                    if (rowToggled) {
                        currentValue = 1 - currentValue;
                    }
                    if (currentValue == 1) {
                        onesInCol++;
                    }
                }
                
                // Decide whether to toggle the column to maximize 1s
                int colContribution = Math.max(onesInCol, m - onesInCol);
                currentScore += colContribution * (1 << (n - 1 - c));
            }
            
            maxScore = Math.max(maxScore, currentScore);
        }
        return maxScore;
    }
}
```
### Algorithm
- Initialize `max_score` to 0.
- Iterate through all `2^m` possible row-toggle combinations using a bitmask `i` from `0` to `2^m - 1`.
- For each combination `i`:
  - Initialize `current_score` to 0.
  - For each column `j` from `0` to `n-1`:
    - Count the number of `1`s (`ones_in_col`) in this column, considering the row toggles specified by `i`.
    - The optimal number of `1`s for this column is `max(ones_in_col, m - ones_in_col)`.
    - Add `max(ones_in_col, m - ones_in_col) * (1 << (n - 1 - j))` to `current_score`.
  - Update `max_score = max(max_score, current_score)`.
- Return `max_score`.

## Greedy Approach
A much more efficient approach is a greedy one. The key observation is that the leftmost column has the highest impact on the total score because it represents the most significant bit (MSB) of each row's number. To maximize the total score, we should try to make each row's number as large as possible, which starts with making its MSB a `1`.
**Time:** O(m * n). We iterate through the grid once to calculate the contributions of all columns. · **Space:** O(1) extra space. We only use a few variables to keep track of the score and counts.
**Pros:** Highly efficient with a linear time complexity of O(m*n).; Optimal solution is guaranteed by the greedy choice property.; Simple to implement and requires no extra space.
**Cons:** The greedy logic might not be immediately obvious without analyzing the problem structure and the significance of bit positions.
### Explanation
The strategy consists of two main steps:
1.  **Row Optimization:** Iterate through each row of the matrix. If the first element of a row (`grid[i][0]`) is `0`, we toggle that entire row. This ensures that the first column becomes all `1`s. This move is always optimal because flipping a row starting with `0` guarantees an increase in its value. The gain from the MSB (`2^(n-1)`) outweighs any potential loss from the other bits (at most `2^(n-1) - 1`). After this step, we should not perform any more row toggles, as it would make an MSB `0`.
2.  **Column Optimization:** After fixing the rows, we optimize the columns. For each column `j` (from `1` to `n-1`), we count the number of `1`s. If the number of `0`s is greater than the number of `1`s, we toggle the column. This maximizes the number of `1`s in that column, thereby maximizing its contribution to the total score. This decision for each column is independent and does not affect the optimality of other columns.

Instead of actually modifying the grid, we can calculate the score directly. The first column will contribute `m * 2^(n-1)` to the score. For every other column, we calculate how many `1`s it would have after the initial row flips, and then decide if a column flip would be beneficial.

Here is the implementation in Java:
```java
class Solution {
    public int matrixScore(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // The score is calculated by summing the contributions of each column.
        // The contribution of column j is (number of 1s in column j) * 2^(n-1-j).

        // First, handle the first column (MSB). We want all 1s.
        // This is achieved by flipping any row that starts with a 0.
        // The contribution of the first column is always m * 2^(n-1).
        int score = m * (1 << (n - 1));

        // Now, handle the other columns.
        for (int j = 1; j < n; j++) {
            int onesInCol = 0;
            // For each column, count the number of 1s after the initial row flips.
            for (int i = 0; i < m; i++) {
                // A row is flipped if grid[i][0] == 0.
                // The value at grid[i][j] becomes 1 - grid[i][j] if the row is flipped.
                // A clever way to check the final value:
                // If grid[i][0] == grid[i][j], the value after row flip is 1.
                // (e.g., 1==1 -> 1; 0==0 -> 1-0=1)
                // If grid[i][0] != grid[i][j], the value after row flip is 0.
                // (e.g., 1!=0 -> 0; 0!=1 -> 1-1=0)
                if (grid[i][j] == grid[i][0]) {
                    onesInCol++;
                }
            }
            
            // For this column, we can either have 'onesInCol' 1s or 'm - onesInCol' 1s (if we flip it).
            // We choose the maximum to maximize the score.
            int maxOnes = Math.max(onesInCol, m - onesInCol);
            
            // Add this column's contribution to the total score.
            score += maxOnes * (1 << (n - 1 - j));
        }

        return score;
    }
}
```
### Algorithm
- Get matrix dimensions `m` and `n`.
- Calculate the score contribution from the first column. Since we want all `1`s in the most significant column, its contribution is `m * (1 << (n - 1))`.
- Initialize `score` with this value.
- For each subsequent column `j` from `1` to `n-1`:
  - Initialize `ones_in_col = 0`.
  - For each row `i` from `0` to `m-1`:
    - Determine the effective value at `(i, j)` after the initial row flips. A row `i` is flipped if `grid[i][0] == 0`. The effective value at `(i,j)` is `1` if `grid[i][j] == grid[i][0]`, and `0` otherwise.
    - Add this effective value to `ones_in_col`.
  - The maximum number of `1`s we can get in this column is `max(ones_in_col, m - ones_in_col)`.
  - Add `max(ones_in_col, m - ones_in_col) * (1 << (n - 1 - j))` to the total `score`.
- Return `score`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int MatrixScore(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        for (int i = 0; i < m; ++i) {
            if (grid[i][0] == 0) {
                for (int j = 0; j < n; ++j) {
                    grid[i][j] ^= 1;
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < n; ++j) {
            int cnt = 0;
            for (int i = 0; i < m; ++i) {
                if (grid[i][j] == 1) {
                    ++cnt;
                }
            }
            ans += Math.Max(cnt, m - cnt) * (1 << (n - j - 1));
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int matrixScore(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; ++i) {
      if (grid[i][0] == 0) {
        for (int j = 0; j < n; ++j) {
          grid[i][j] ^= 1;
        }
      }
    }
    int ans = 0;
    for (int j = 0; j < n; ++j) {
      int cnt = 0;
      for (int i = 0; i < m; ++i) {
        cnt += grid[i][j];
      }
      ans += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int matrixScore(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    for (int i = 0; i < m; ++i) {
      if (grid[i][0] == 0) {
        for (int j = 0; j < n; ++j) {
          grid[i][j] ^= 1;
        }
      }
    }
    int ans = 0;
    for (int j = 0; j < n; ++j) {
      int cnt = 0;
      for (int i = 0; i < m; ++i) {
        cnt += grid[i][j];
      }
      ans += max(cnt, m - cnt) * (1 << (n - j - 1));
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int: 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 ans = 0 for j in range(n): cnt = sum(grid[i][j] for i in range(m)) ans += max(cnt, m - cnt) * (1 << (n - j - 1)) return ans

```