Score After Flipping Matrix — Solution in Python, Java & C++
Score After Flipping Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Score After Flipping Matrix is a medium coding problem on arrays, greedy and matrix, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Greedy, Matrix, Bit Manipulation
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n binary matrix grid. A move picks one whole row or one whole column and toggles every cell in it (0 becomes 1, 1 becomes 0). You may make any number of moves.
Afterwards each row is read as a binary number, most significant bit on the left, and the score is the sum of these numbers.
Return the highest score you can reach.
Example 1
Input: grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
Output: 39
Explanation: Flip row 0, then columns 2 and 3: rows read 1111, 1001, 1111 = 15 + 9 + 15.
Example 2
Input: grid = [[1,0,1],[0,1,1]]
Output: 13
Example 3
Input: grid = [[0]]
Output: 1
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 20grid[i][j] is 0 or 1
Hints for Score After Flipping Matrix
Hint 1
The leftmost bit of a row is worth more than all the other bits of that row combined.
Hint 2
So every row should start with a 1 — flip the rows that start with 0.
Hint 3
After that, columns are independent: flip a column whenever it has more zeros than ones.
How to solve Score After Flipping Matrix
The leading bit dominates: 2^(n-1) exceeds the sum of all lower bits. So first make every row start with 1 using row flips, then choose each remaining column's flip by majority.
Approach
- Conceptually flip every row whose first cell is 0. A cell
(i, j)then holds 1 exactly whengrid[i][j] == grid[i][0]. - For each column
j, countonesunder that rule and takemax(ones, m - ones)— flipping the column if zeros are the majority. - Add
max(ones, m - ones) · 2^(n - 1 - j)to the score.
Why it works
Any row with a leading 0 loses 2^(n-1), more than it can gain from the rest of its bits, so an optimal answer has every leading bit 1 (column 0 is never flipped afterwards). Once the row flips are fixed, column flips do not interact: each column contributes its count of ones times its place value, and flipping it swaps ones for m - ones.
Complexity
- Time —
O(m · n) - Space —
O(1)
Pitfalls
- Do not flip column 0 after fixing the rows — it is already all ones.
- Count a cell as 1 after the row flip, i.e. compare it to the row's first cell rather than reading the raw value.
- With
n <= 20the score stays below20 · 2^20, so 32-bit integers suffice.
Reference solution
Python
from typing import List
def matrixScore(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
total = 0
for j in range(n):
ones = sum(1 for i in range(m) if grid[i][j] == grid[i][0])
total += max(ones, m - ones) << (n - 1 - j)
return totalJava
public static int matrixScore(int[][] grid) {
int m = grid.length, n = grid[0].length;
int total = 0;
for (int j = 0; j < n; j++) {
int ones = 0;
for (int i = 0; i < m; i++) if (grid[i][j] == grid[i][0]) ones++;
total += Math.max(ones, m - ones) * (1 << (n - 1 - j));
}
return total;
}C++
int matrixScore(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int total = 0;
for (int j = 0; j < n; j++) {
int ones = 0;
for (int i = 0; i < m; i++) if (grid[i][j] == grid[i][0]) ones++;
total += max(ones, m - ones) * (1 << (n - 1 - j));
}
return total;
}JavaScript
var matrixScore = function(grid) {
var m = grid.length, n = grid[0].length;
var total = 0;
for (var j = 0; j < n; j++) {
var ones = 0;
for (var i = 0; i < m; i++) if (grid[i][j] === grid[i][0]) ones++;
total += Math.max(ones, m - ones) * (1 << (n - 1 - j));
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Greedy Algorithms