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
- 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. - After that, the leading bit of every row is fixed to 1 and rows can no longer be flipped profitably.
- For each remaining column
j, count the ones; the column can be flipped independently, so takemax(ones, m - ones). - 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
jis 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.