Watch 10 video solutions for Score After Flipping Matrix, a medium level problem involving Array, Greedy, Bit Manipulation. This walkthrough by NeetCodeIO has 11,301 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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.lengthn == grid[i].length1 <= m, n <= 20grid[i][j] is either 0 or 1.Problem Overview: You are given a binary m x n matrix. You may flip any row or column (toggle 0 ↔ 1). After all flips, each row represents a binary number. The goal is to maximize the total sum of these row values.
Approach 1: Row Flip to Maximize Binary Leading Ones (O(m*n) time, O(1) space)
The most significant bit of each row is the first column, so maximizing the score starts by ensuring every row begins with 1. Iterate through the matrix and flip any row whose first element is 0. After this step, all rows contribute the largest possible leading bit. Next, examine each remaining column and count the number of 1s. If a column contains fewer 1s than 0s, flip the column to maximize the contribution of that bit position. Finally, compute the binary value of each row and sum them. The approach relies on greedy decisions that maximize higher-order bits first, which dominate the final score. This method works directly on the matrix and uses constant extra space.
Approach 2: Greedy Columns Majority Principle (O(m*n) time, O(1) space)
This optimization avoids actually flipping rows. Instead, treat every row with a leading 0 as if it were flipped. Since the first column should always be 1, its contribution is m * 2^(n-1). For each subsequent column, count how many rows would have a 1 after the potential row flip. The value of a cell becomes grid[r][c] if the first bit is 1, otherwise 1 - grid[r][c]. Choose the majority between 1s and 0s to simulate the best column flip, then add its weighted contribution count * 2^(n-c-1). This greedy counting technique computes the maximum score without modifying the matrix. The logic relies on properties of binary numbers and majority counts in each column.
The solution relies heavily on concepts from greedy algorithms, since each decision locally maximizes the most valuable bit. The matrix structure makes iteration straightforward using standard array traversal, while binary weighting connects naturally to bit manipulation techniques.
Recommended for interviews: The Greedy Columns Majority approach. Interviewers expect you to recognize that the first column must always be 1 and that column decisions depend only on majority counts after virtual row flips. Implementing the brute row-flip simulation shows understanding, but the counting-based greedy method demonstrates stronger reasoning about binary weights and optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Row Flip to Maximize Binary Leading Ones | O(m*n) | O(1) | Best when you want a straightforward simulation of row and column flips. |
| Greedy Columns Majority Principle | O(m*n) | O(1) | Preferred for interviews; avoids physical flips and computes score using column majority logic. |