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.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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n), as each element in the matrix grid is visited once. Space Complexity: O(1), operating in-place.
| 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. |
Score After Flipping Matrix - Leetcode 861 - Python • NeetCodeIO • 10,604 views views
Watch 9 more video solutions →Practice Score After Flipping Matrix with our built-in code editor and test cases.
Practice on FleetCode