Score After Flipping Matrix

How it works

We can compute the score without modifying the grid. After row flips to ensure all first bits are 1, we know every row contributes 2^(COLS - 1) from the first column. For other columns, instead of tracking the actual values, we count how many cells would be 1 after both row and column optimizations. A cell is effectively 1 if it differs from the first cell in its row (since the first cell becomes 1 after row flip). We then take the maximum of this count and its complement for each column.

Steps

1. Initialize the result with ROWS * 2^(COLS - 1) (all first bits are 1).
2. For each column c from 1 to COLS - 1:
   • Count cells that differ from the first cell in their row.
   • Take the maximum of this cnt and ROWS - cnt (the better choice after potential column flip).
   • Add cnt * 2^(COLS - c - 1) to the result.
3. Return the result.

Complexity

• Time complexity: O(m * n)
• Space complexity: O(1) extra space.

Where m is the number of rows and n is the number of columns.

Things to watch for

Flipping Columns Before Rows

A critical ordering mistake is flipping columns before ensuring all first bits are 1. Row flips must happen first because they determine which cells need flipping in each row. Flipping columns first may undo progress or lead to suboptimal results since the leftmost bit has the highest value.

Flipping Columns When 1s Equal 0s

When a column has exactly half 1s and half 0s, flipping it makes no difference to the score. Some solutions incorrectly flip in this case or use <= instead of < in the comparison. Only flip when 0s strictly outnumber 1s to avoid unnecessary operations.

Miscalculating Bit Position Values

When computing the final score, using incorrect powers of 2 for each column position causes wrong answers. The leftmost column contributes 2^(COLS-1), not 2^0. Ensure you use COLS - c - 1 as the exponent for column c when calculating each bit's contribution.

from typing import List

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        res = ROWS * (1 << (COLS - 1))

        for c in range(1, COLS):
            cnt = 0
            for r in range(ROWS):
                if grid[r][c] != grid[r][0]:
                    cnt += 1

            cnt = max(cnt, ROWS - cnt)
            res += cnt * (1 << (COLS - c - 1))

        return res

class Solution {
public:
    int matrixScore(vector<vector<int>>& grid) {
        int ROWS = grid.size(), COLS = grid[0].size();
        int res = ROWS * (1 << (COLS - 1));

        for (int c = 1; c < COLS; c++) {
            int cnt = 0;
            for (int r = 0; r < ROWS; r++) {
                if (grid[r][c] != grid[r][0]) {
                    cnt++;
                }
            }
            cnt = max(cnt, ROWS - cnt);
            res += cnt * (1 << (COLS - c - 1));
        }
        return res;
    }
};