Score After Flipping Matrix solution and explanation
Google
9 more videos on this problem
Score After Flipping Matrix - Leetcode 861 - PythonNeetCodeIO · 22:30 · 11K views
Score After Flipping Matrix | Modifying | Without Modifying Input | Leetcode 861 | codestorywithMIKcodestorywithMIK · 35:26 · 8K views
861. Score After Flipping Matrix | Greedy | Bit Manipulation | 2 Approaches | O(1) spaceAryan Mittal · 15:23 · 6K views
Score After Flipping Matrix (Leetcode 861)Algorithms Casts · 25:20 · 1K views
LeetCode 861 - Score After Flipping Matrix - JavaAlpha-Code · 19:25 · 214 views
861. Score After Flipping MatrixUnplug Nate · 6:35 · 124 views
Leetcode Daily Challenge - 861. Score After Flipping MatrixAtomicCoding · 15:15 · 77 views
861. Score After Flipping Matrix | LeetCode POTD | BIT MANIPULATION | TUTORIAL - 41Coding Kart · 13:47 · 73 views
💡MAXIMIZE SCORE ! | 861. Score After Flipping Matrix | Today's POTD | 13th May 2024Nikhil Richhariya · 8:00 · 65 views
861. Score After Flipping Matrix (leetcode)LeetDaily · 5:52 · 54 views
The problem
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 either0or1.
Approach overview
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 1: Row Flip to Maximize Binary Leading Ones
To maximize the score, we should ensure that the leftmost bit (most significant bit) of each binary number (row) is 1. If the first bit of any row is 0, we can flip that entire row.
Once the leading bits are all 1, we maximize further by toggling columns where the count of 0s is more than 1s. This ensures that the binary numbers are as large as possible.
class Solution:
def matrixScore(self, grid):
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
score = 0
for j in range(n):
col_count = sum(grid[i][j] for i in range(m))
col_count = max(col_count, m - col_count)
score += col_count * (1 << (n - j - 1))
return scoreclass Solution {
public int matrixScore(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int score = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][0] == 0) {
for (int j = 0; j < n; ++j) {
grid[i][j] ^= 1;
}
}
}
for (int j = 0; j < n; j++) {
int colCount = 0;
for (int i = 0; i < m; i++) {
if (grid[i][j] == 1) {
colCount++;
}
}
colCount = Math.max(colCount, m - colCount);
score += colCount * (1 << (n - j - 1));
}
return score;
}
}#include <vector>
#include <cmath>
using namespace std;
class Solution {
public:
int matrixScore(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int score = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][0] == 0) {
for (int j = 0; j < n; ++j) {
grid[i][j] ^= 1;
}
}
}
for (int j = 0; j < n; ++j) {
int colCount = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == 1) {
colCount++;
}
}
colCount = max(colCount, m - colCount);
score += colCount * (1 << (n - j - 1));
}
return score;
}
};var matrixScore = function(grid) {
const m = grid.length;
const n = grid[0].length;
for (let i = 0; i < m; i++) {
if (grid[i][0] === 0) {
for (let j = 0; j < n; j++) {
grid[i][j] ^= 1;
}
}
}
let score = 0;
for (let j = 0; j < n; j++) {
let colCount = 0;
for (let i = 0; i < m; i++) {
if (grid[i][j] === 1) {
colCount++;
}
}
colCount = Math.max(colCount, m - colCount);
score += colCount * (1 << (n - j - 1));
}
return score;
};#include <stdio.h>
#include <math.h>
int matrixScore(int** grid, int gridSize, int* gridColSize) {
int m = gridSize;
int n = gridColSize[0];
int score = 0;
// Step 1: Ensure the first column is all ones
for (int i = 0; i < m; ++i) {
if (grid[i][0] == 0) {
for (int j = 0; j < n; ++j) {
grid[i][j] ^= 1;
}
}
}
// Step 2: For each column (except the first), maximize the number of 1s
for (int j = 0; j < n; ++j) {
int colCount = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == 1) {
colCount++;
}
}
colCount = fmax(colCount, m - colCount);
score += colCount * (1 << (n - j - 1));
}
return score;
}public class Solution {
public int MatrixScore(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
int score = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][0] == 0) {
for (int j = 0; j < n; ++j) {
grid[i][j] ^= 1;
}
}
}
for (int j = 0; j < n; ++j) {
int colCount = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == 1) {
colCount++;
}
}
colCount = Math.Max(colCount, m - colCount);
score += colCount * (1 << (n - j - 1));
}
return score;
}
}The Python solution uses a nested loop to first convert any row with a zero as its first column value into a row starting with one. Then, it optimizes each column to ensure maximum contribution to the score.
Time Complexity: O(m * n), where m and n are the dimensions of the grid, due to the loops. Space Complexity: O(1), as the grid is used in place.
Approach 2: Greedy Columns Majority Principle
This approach differs slightly by treating the majority of 1s per column as more influential. Instead of flipping rows first, the solution primarily ensures maximal 1 presence per column, beginning with the columns themselves.
class Solution:
def matrixScore(self, grid):
m, n = len(grid), len(grid[0])
score = (1 << (n - 1)) * m # Assume the left-most bit is optimized.
for j in range(1, n):
col_count = 0
for i in range(m):
if grid[i][j] == grid[i][0]: # Match with first column
col_count += 1
col_count = max(col_count, m - col_count)
score += col_count * (1 << (n - j - 1))
return scoreclass Solution {
public int matrixScore(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int score = (1 << (n - 1)) * m;
for (int j = 1; j < n; j++) {
int colCount = 0;
for (int i = 0; i < m; i++) {
if (grid[i][j] == grid[i][0]) colCount++;
}
colCount = Math.max(colCount, m - colCount);
score += colCount * (1 << (n - j - 1));
}
return score;
}
}#include <vector>
#include <cmath>
using namespace std;
class Solution {
public:
int matrixScore(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int score = (1 << (n-1)) * m;
for (int j = 1; j < n; ++j) {
int colCount = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == grid[i][0]) colCount++;
}
colCount = max(colCount, m - colCount);
score += colCount * (1 << (n - j - 1));
}
return score;
}
};var matrixScore = function(grid) {
const m = grid.length;
const n = grid[0].length;
let score = (1 << (n-1)) * m; // Assume left-most bits optimized already.
for (let j = 1; j < n; j++) {
let colCount = 0;
for (let i = 0; i < m; i++) {
if (grid[i][j] == grid[i][0]) colCount++;
}
colCount = Math.max(colCount, m - colCount);
score += colCount * (1 << (n - j - 1));
}
return score;
};#include <stdio.h>
#include <math.h>
int matrixScore(int** grid, int gridSize, int* gridColSize) {
int m = gridSize;
int n = gridColSize[0];
int score = (1 << (n-1)) * m; // Start with most significant bits settled.
for (int j = 1; j < n; ++j) {
int colCount = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == grid[i][0]) { // Count matching the first column's leading bit.
colCount++;
}
}
colCount = fmax(colCount, m - colCount);
score += colCount * (1 << (n - j - 1));
}
return score;
}public class Solution {
public int MatrixScore(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
int score = (1 << (n - 1)) * m;
for (int j = 1; j < n; ++j) {
int colCount = 0;
for (int i = 0; i < m; ++i) {
if (grid[i][j] == grid[i][0]) colCount++;
}
colCount = Math.Max(colCount, m - colCount);
score += colCount * (1 << (n - j - 1));
}
return score;
}
}In Python, the algorithm immediately accounts for the most significant bit interactions and adjusts subsequent digits based on perception and binary values.
Time Complexity: O(m * n), a conventional grid parsing speed. Space Complexity: O(1), leveraging original grid space.
Approach 3: Default Approach
function matrixScore(grid: number[][]): number {
const m = grid.length;
const n = grid[0].length;
for (let i = 0; i < m; ++i) {
if (grid[i][0] == 0) {
for (let j = 0; j < n; ++j) {
grid[i][j] ^= 1;
}
}
}
let ans = 0;
for (let j = 0; j < n; ++j) {
let cnt = 0;
for (let i = 0; i < m; ++i) {
cnt += grid[i][j];
}
ans += Math.max(cnt, m - cnt) * (1 << (n - j - 1));
}
return ans;
}func matrixScore(grid [][]int) int {
m, n := len(grid), len(grid[0])
for i := 0; i < m; i++ {
if grid[i][0] == 0 {
for j := 0; j < n; j++ {
grid[i][j] ^= 1
}
}
}
ans := 0
for j := 0; j < n; j++ {
cnt := 0
for i := 0; i < m; i++ {
cnt += grid[i][j]
}
if cnt < m-cnt {
cnt = m - cnt
}
ans += cnt * (1 << (n - j - 1))
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Row Flip to Maximize Binary Leading Ones | Time Complexity: O(m * n), where m and n are the dimensions of the grid, due to the loops. Space Complexity: O(1), as the grid is used in place. |
| Greedy Columns Majority Principle | Time Complexity: O(m * n), a conventional grid parsing speed. Space Complexity: O(1), leveraging original grid space. |
| Default Approach | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Score After Flipping Matrix easy or hard?
Score After Flipping Matrix is classified as a Medium problem. The implementation is simple once you recognize the greedy insight that the first column must always be 1 and that column decisions depend on maximizing the number of 1s.
How to solve Score After Flipping Matrix in O(m*n)?
First ensure the most significant bit of every row is 1 by virtually flipping rows whose first column is 0. Then iterate through each column and count how many 1s would appear after that adjustment. Choose the larger of ones or zeros for that column and add its weighted binary contribution to the total score.
What is the best approach for Score After Flipping Matrix?
The optimal approach is a greedy strategy that ensures the first column of every row is 1 and then maximizes the number of 1s in each remaining column. By treating rows with leading 0 as virtually flipped and applying a column majority rule, you compute the maximum possible score in O(m*n) time and O(1) space.
What data structure is used in Score After Flipping Matrix?
The problem primarily uses a 2D array (matrix) to represent the grid. The algorithm relies on greedy analysis and simple counting rather than advanced data structures, though bit manipulation concepts help when calculating binary weights.
What is the time complexity of Score After Flipping Matrix?
The optimal solution runs in O(m*n) time where m is the number of rows and n is the number of columns. Each cell is inspected at most once while computing column contributions. The space complexity remains O(1) since the calculation can be done without extra data structures.
Score After Flipping Matrix Python or Java solution approach?
Python and Java implementations typically follow the same greedy pattern: ensure the first column is effectively all 1s, then evaluate each column using majority counts. The code iterates through the matrix and accumulates the weighted score based on binary positions.
Is Score After Flipping Matrix asked at Google, Amazon, or Meta?
Matrix greedy optimization problems like Score After Flipping Matrix frequently appear in technical interviews at companies such as Amazon, Google, and Meta. The problem tests reasoning about binary values, greedy choices, and efficient traversal of a matrix.