861. Score After Flipping Matrix - Explanation

Problem Link

1. Greedy (Overwriting the Input)

Intuition

Each row represents a binary number, and higher-order bits contribute more to the total score. The leftmost bit has the highest value, so we want it to be 1 in every row. First, flip any row where the first bit is 0. After that, for each column, we want to maximize the number of 1s. If a column has more 0s than 1s, flip it. This greedy strategy ensures we maximize the score by prioritizing high-value bits.

Algorithm

1. For each row, if the first element is 0, flip the entire row using XOR.
2. For each column (starting from column 1), count the number of 1s.
   • If 0s outnumber 1s, flip the entire column.
3. Calculate the final score by summing each cell's contribution:
   • A cell at column c contributes value * 2^(COLS - c - 1) to the total.
4. Return the total res.

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

        for r in range(ROWS):
            if grid[r][0] == 0:
                for c in range(COLS):
                    grid[r][c] ^= 1

        for c in range(COLS):
            one_cnt = sum(grid[r][c] for r in range(ROWS))
            if one_cnt < ROWS - one_cnt:
                for r in range(ROWS):
                    grid[r][c] ^= 1

        res = 0
        for r in range(ROWS):
            for c in range(COLS):
                res += grid[r][c] << (COLS - c - 1)

        return res

Time & Space 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.

---

2. Greedy (Optimal)

Intuition

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.

Algorithm

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.

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

Time & Space 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.

Common Pitfalls

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.