Score After Flipping Matrix
MedPrompt
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 = 39Example 2:
Input: grid = [[0]]
Output: 1
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 20grid[i][j]is either0or1.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach explores every possible combination of row toggles. Since toggling a row twice is the same as not toggling it at all, for each of the m rows, we have two choices: either toggle it or not. This gives 2^m possible configurations of the matrix based on row toggles. For each of these configurations, we can then determine the optimal column toggles to maximize the score.
Algorithm
- Initialize
max_scoreto 0. - Iterate through all
2^mpossible row-toggle combinations using a bitmaskifrom0to2^m - 1. - For each combination
i:- Initialize
current_scoreto 0. - For each column
jfrom0ton-1:- Count the number of
1s (ones_in_col) in this column, considering the row toggles specified byi. - The optimal number of
1s for this column ismax(ones_in_col, m - ones_in_col). - Add
max(ones_in_col, m - ones_in_col) * (1 << (n - 1 - j))tocurrent_score.
- Count the number of
- Update
max_score = max(max_score, current_score).
- Initialize
- Return
max_score.
Walkthrough
The core idea is to iterate through all 2^m possibilities for flipping the rows. We can use a bitmask from 0 to 2^m - 1 to represent which rows to flip. If the i-th bit is set in the mask, we consider row i as flipped.
For each of the 2^m row-flipped states:
- We determine the best possible score. With the rows fixed, the decision to flip each column is independent.
- For each column, we count the number of
1s. If flipping the column (changing1s to0s and vice-versa) results in more1s, we do it. This means we choose the configuration with more1s for each column. - The score for the current row-flip combination is calculated by summing the contributions of each column, where each column is optimally configured.
- We keep track of the maximum score found across all
2^mconfigurations. This exhaustive search over row combinations guarantees finding the optimal solution, as any final configuration can be achieved by some set of row and column flips.
Here is the implementation in Java:
class Solution { public int matrixScore(int[][] grid) { int m = grid.length; int n = grid[0].length; int maxScore = 0; // Iterate through all 2^m row toggle combinations using a bitmask for (int i = 0; i < (1 << m); i++) { int currentScore = 0; // For each column, calculate its contribution to the score for (int c = 0; c < n; c++) { int onesInCol = 0; // Count the number of 1s in the current column after row toggles for (int r = 0; r < m; r++) { // Check if row 'r' should be toggled boolean rowToggled = (i & (1 << r)) != 0; int currentValue = grid[r][c]; if (rowToggled) { currentValue = 1 - currentValue; } if (currentValue == 1) { onesInCol++; } } // Decide whether to toggle the column to maximize 1s int colContribution = Math.max(onesInCol, m - onesInCol); currentScore += colContribution * (1 << (n - 1 - c)); } maxScore = Math.max(maxScore, currentScore); } return maxScore; }}Complexity
Time
O(2^m * m * n). We iterate `2^m` times for each row combination. Inside the loop, we iterate through each cell of the matrix (`m*n`) to calculate the score for that combination.
Space
O(1) extra space. The calculation is done on the fly without creating a temporary grid.
Trade-offs
Pros
It is guaranteed to find the optimal solution by exhaustively checking all row-flip possibilities.
The logic is a direct, albeit inefficient, interpretation of the problem's move set.
Cons
The exponential time complexity with respect to the number of rows (
m) makes it too slow for larger values ofm.It is significantly less efficient than the greedy approach.
A much more efficient approach is a greedy one. The key observation is that the leftmost column has the highest impact on the total score because it represents the most significant bit (MSB) of each row's number. To maximize the total score, we should try to make each row's number as large as possible, which starts with making its MSB a 1.
Algorithm
- Get matrix dimensions
mandn. - Calculate the score contribution from the first column. Since we want all
1s in the most significant column, its contribution ism * (1 << (n - 1)). - Initialize
scorewith this value. - For each subsequent column
jfrom1ton-1:- Initialize
ones_in_col = 0. - For each row
ifrom0tom-1:- Determine the effective value at
(i, j)after the initial row flips. A rowiis flipped ifgrid[i][0] == 0. The effective value at(i,j)is1ifgrid[i][j] == grid[i][0], and0otherwise. - Add this effective value to
ones_in_col.
- Determine the effective value at
- The maximum number of
1s we can get in this column ismax(ones_in_col, m - ones_in_col). - Add
max(ones_in_col, m - ones_in_col) * (1 << (n - 1 - j))to the totalscore.
- Initialize
- Return
score.
Walkthrough
The strategy consists of two main steps:
- Row Optimization: Iterate through each row of the matrix. If the first element of a row (
grid[i][0]) is0, we toggle that entire row. This ensures that the first column becomes all1s. This move is always optimal because flipping a row starting with0guarantees an increase in its value. The gain from the MSB (2^(n-1)) outweighs any potential loss from the other bits (at most2^(n-1) - 1). After this step, we should not perform any more row toggles, as it would make an MSB0. - Column Optimization: After fixing the rows, we optimize the columns. For each column
j(from1ton-1), we count the number of1s. If the number of0s is greater than the number of1s, we toggle the column. This maximizes the number of1s in that column, thereby maximizing its contribution to the total score. This decision for each column is independent and does not affect the optimality of other columns.
Instead of actually modifying the grid, we can calculate the score directly. The first column will contribute m * 2^(n-1) to the score. For every other column, we calculate how many 1s it would have after the initial row flips, and then decide if a column flip would be beneficial.
Here is the implementation in Java:
class Solution { public int matrixScore(int[][] grid) { int m = grid.length; int n = grid[0].length; // The score is calculated by summing the contributions of each column. // The contribution of column j is (number of 1s in column j) * 2^(n-1-j). // First, handle the first column (MSB). We want all 1s. // This is achieved by flipping any row that starts with a 0. // The contribution of the first column is always m * 2^(n-1). int score = m * (1 << (n - 1)); // Now, handle the other columns. for (int j = 1; j < n; j++) { int onesInCol = 0; // For each column, count the number of 1s after the initial row flips. for (int i = 0; i < m; i++) { // A row is flipped if grid[i][0] == 0. // The value at grid[i][j] becomes 1 - grid[i][j] if the row is flipped. // A clever way to check the final value: // If grid[i][0] == grid[i][j], the value after row flip is 1. // (e.g., 1==1 -> 1; 0==0 -> 1-0=1) // If grid[i][0] != grid[i][j], the value after row flip is 0. // (e.g., 1!=0 -> 0; 0!=1 -> 1-1=0) if (grid[i][j] == grid[i][0]) { onesInCol++; } } // For this column, we can either have 'onesInCol' 1s or 'm - onesInCol' 1s (if we flip it). // We choose the maximum to maximize the score. int maxOnes = Math.max(onesInCol, m - onesInCol); // Add this column's contribution to the total score. score += maxOnes * (1 << (n - 1 - j)); } return score; }}Complexity
Time
O(m * n). We iterate through the grid once to calculate the contributions of all columns.
Space
O(1) extra space. We only use a few variables to keep track of the score and counts.
Trade-offs
Pros
Highly efficient with a linear time complexity of O(m*n).
Optimal solution is guaranteed by the greedy choice property.
Simple to implement and requires no extra space.
Cons
The greedy logic might not be immediately obvious without analyzing the problem structure and the significance of bit positions.
Solutions
Solution
public class Solution { public int MatrixScore(int[][] grid) { int m = grid.Length, n = grid[0].Length; for (int i = 0; i < m; ++i) { if (grid[i][0] == 0) { for (int j = 0; j < n; ++j) { grid[i][j] ^= 1; } } } int ans = 0; for (int j = 0; j < n; ++j) { int cnt = 0; for (int i = 0; i < m; ++i) { if (grid[i][j] == 1) { ++cnt; } } ans += Math.Max(cnt, m - cnt) * (1 << (n - j - 1)); } return ans; }}class Solution {public int matrixScore(int[][] grid) { int m = grid.length, n = grid[0].length; for (int i = 0; i < m; ++i) { if (grid[i][0] == 0) { for (int j = 0; j < n; ++j) { grid[i][j] ^= 1; } } } int ans = 0; for (int j = 0; j < n; ++j) { int cnt = 0; for (int i = 0; i < m; ++i) { cnt += grid[i][j]; } ans += Math.max(cnt, m - cnt) * (1 << (n - j - 1)); } return ans; }}class Solution {public: int matrixScore(vector<vector<int>> &grid) { int m = grid.size(), n = grid[0].size(); for (int i = 0; i < m; ++i) { if (grid[i][0] == 0) { for (int j = 0; j < n; ++j) { grid[i][j] ^= 1; } } } int ans = 0; for (int j = 0; j < n; ++j) { int cnt = 0; for (int i = 0; i < m; ++i) { cnt += grid[i][j]; } ans += max(cnt, m - cnt) * (1 << (n - j - 1)); } return ans; }};class Solution: def matrixScore(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) for i in range(m): if grid[i][0] == 0: for j in range(n): grid[i][j] ^= 1 ans = 0 for j in range(n): cnt = sum(grid[i][j] for i in range(m)) ans += max(cnt, m - cnt) * (1 << (n - j - 1)) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.