Score After Flipping Matrix - Solution & Explanation
Problem Statement
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.
The C solution uses a two-step approach. First, it ensures the first column is all 1s by flipping rows if needed. Then, it checks each column from the second to maximize the count of 1s, flipping the column if 0s are more frequent.
Complexity
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid. Space Complexity: O(1), using inplace modifications.
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.
The C version starts by assuming the most significant bit is maximized by default, adjusting columns to keep or swap based on more 1s than 0s.
Complexity
Time Complexity: O(m * n), as each element in the matrix grid is visited once. Space Complexity: O(1), operating in-place.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Row Flip to Maximize Binary Leading Ones | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid. Space Complexity: O(1), using inplace modifications. |
| Greedy Columns Majority Principle | Time Complexity: O(m * n), as each element in the matrix grid is visited once. Space Complexity: O(1), operating in-place. |
| Default Approach | — |
Detailed 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. |
Video Solution
Score After Flipping Matrix - Leetcode 861 - Python • NeetCodeIO • 11,419 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Score After Flipping Matrix easy or hard?
How to solve Score After Flipping Matrix in O(m*n)?
What is the best approach for Score After Flipping Matrix?
What data structure is used in Score After Flipping Matrix?
What is the time complexity of Score After Flipping Matrix?
Score After Flipping Matrix Python or Java solution approach?
Is Score After Flipping Matrix asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Score After Flipping Matrix with our built-in code editor and test cases.
Practice on FleetCode