⚡Flashcard Drill➔
NeetCode #812LC-861MediumGreedy
← Back to All Problems

#812 · #861 · Score After Flipping Matrix(翻转矩阵后的得分)

📌 Problem Statement & Constraints

You are given an m x n binary matrix grid. A move picks any row or column and flips every value in it. The score of the matrix is the sum, over rows, of the row interpreted as a binary number. Maximise the score. Constraints: 1 <= m, n <= 20, grid[i][j] is 0 or 1.

💡 Core Algorithmic Approaches

  1. The leading column carries the most weight (2^(n-1) per row), so flipping rows to make column 0 all ones is always worth it.
  2. After that, the leading bit of every row is fixed to 1 and rows can no longer be flipped profitably.
  3. For each remaining column j, count the ones; the column can be flipped independently, so take max(ones, m - ones).
  4. Column flips do not interact with row flips, which is why the two phases can be decided greedily and independently.

💻 Benchmark Python3 Implementation

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for row in grid:
            if row[0] == 0:                 # flip rows so the leading column is all 1
                for j in range(n):
                    row[j] ^= 1
        for j in range(1, n):
            ones = sum(grid[i][j] for i in range(m))
            if ones < m - ones:             # flip the column if zeros dominate
                for i in range(m):
                    grid[i][j] ^= 1
        return sum(grid[i][j] << (n - 1 - j) for i in range(m) for j in range(n))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): one pass over the grid for each phase.
💾 Space Complexity
O(1) beyond the input matrix.

⚠️ Interview Pitfalls & Follow-ups

  • Weighing the first column incorrectly: it is worth m * 2^(n-1), more than all other columns combined, so it must always be all ones.
  • Flipping rows after flipping columns: once the leading column is fixed, flipping a row would destroy it; the order matters.
  • Recomputing column flips using the original bits: columns are independent, so the count for column j is unaffected by flips of other columns.
  • Using grid[i][j] * 2(n-1-j) with floats**: the bit shift is exact and clearer.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems