861. Score After Flipping Matrix
Problem Description
You are presented with a binary matrix grid
, which is a 2D array containing 0
s and 1
s. Your task is to maximize the "score" of this matrix. The score is calculated by summing up all the rows considered as binary numbers. In order to raise the score, you can perform as many "moves" as you want. A move consists of picking any row or column and flipping all the bits in it; that is, all 0
s are changed to 1
s and vice versa.
For example, if you have a row [1, 0, 1]
and you perform a move, this row will become [0, 1, 0]
.
The primary goal is to find the highest score possible after performing an optimal sequence of moves.
Intuition
The key observation to solve this problem is to realize that the most significant bit in a binary number has the highest value, so it should always be set to 1
to maximize the number. Therefore, the first step is to ensure all rows start with a 1
. If a row starts with a 0
, we flip the entire row.
The next step is to consider each column, starting from the second one since the first column should already have all 1
s after the initial step. At each column, we can maximize the score by making sure that the number of 1
s is greater than or equal to the number of 0
s. If there are more 0
s than 1
s, we flip the entire column. This is because flipping a column doesn't change the leftmost 1
s that we have set in the first step but increases the number of 1
s in the current column, therefore increasing the overall score.
By applying these two steps, first row-wise, then column-wise, we ensure that each bit contributes the maximum possible value to the score of the matrix.
Here's the reasoning for the solution:
- Flip the rows if the first bit is
0
(outer loop over rows). - For each column, count the number of
1
s. If the number is less than half of the total rows, flip the column (inner loop over columns). - Calculate the score by adding the value of each column's bits to the total score.
In the provided code, grid[i][j] ^= 1
is used to flip the bits (using the XOR operator). max(cnt, m - cnt) * (1 << (n - j - 1))
is the calculation of the contribution of each column to the score, choosing to flip the column or not depending on which option gives more 1
s, and then multiplying by the value of the bit position, which decreases as we move right.
Learn more about Greedy patterns.
Solution Approach
The solution takes a greedy approach to maximizing the score of the binary matrix by making sure that the most significant bit of every row is set to 1
and then ensuring that each column contains as many 1
s as possible.
Here's the breakdown of how the code implements the solution:
-
The first loop iterates through each row in the binary matrix
grid
. The size of the matrix is determined bym
rows andn
columns. -
Inside this loop, we check if the first element of the row (
grid[i][0]
) is0
. If so, we flip the entire row using a nested loop which toggles each elementgrid[i][j] ^= 1
. This is done using the XOR operator^
, which will flip a0
to1
and vice versa. -
The outer loop with the variable
j
goes through each column. The inner loop counts the number of1
s in the current column. Instead of flipping each bit when necessary, we're just counting the number of1
s because we can compute the column contribution to the score mathematically, without modifying the matrix. -
For each column, we calculate the maximum possible value it can contribute to the score based on the current state of bits in that column. This is computed by
max(cnt, m - cnt)
. We take the larger value between the number of1
s (cnt
) and the number of0
s (m - cnt
), considering that if the0
s were in the majority, a column flip would change them to1
s. -
The column's contribution to the overall score is then computed by multiplying this maximum number with the binary value of the position. In a binary number, the leftmost bit is the most significant; hence, the value is computed by
1 << (n - j - 1)
, which is equivalent to raising2
to the power of the column's index from the right (0-based). For example, if the column is the second from the right in a4
-column grid, its value is2^(4-2-1) = 2^(1) = 2
. -
This contribution is added to
ans
for each column to build up the total score. -
Once all columns have been processed, the variable
ans
holds the highest possible score, which is returned.
The algorithm efficiently calculates the maximum score possible without needing to actually perform the flips visually or record the state of the matrix after each flip, thanks to mathematical binary operations and the properties of binary numbers.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's take a simple example and walk through the solution approach to understand it better.
Consider the binary matrix, grid
, represented by the following 2D array:
10 1 21 1 30 1
The matrix has 3 rows (m = 3
) and 2 columns (n = 2
). We want to maximize the "score" of this matrix through flips.
Step by Step Solution:
-
Make sure that all rows start with
1
:- Row 1 starts with
0
, so we flip it:0 1
becomes1 0
. - Row 3 also starts with
0
, we flip it:0 1
becomes1 0
.
After this step, our grid looks like this:
1 1 0 2 1 1 3 1 0
- Row 1 starts with
-
Now, we need to maximize
1
s in each column. We note that the first column already has all1
s because of the initial row flips. So we consider the second column. -
Count the number of
1
s in the second column:- There is only 1
1
in the second column.
We want the majority of the bits in each column to be
1
. Since there is only 1 '1' and 2 '0's in the second column, we'll consider this column flipped for maximization purposes. - There is only 1
-
Calculate the contribution of each column to the total score:
- The first column, having all
1
s, contributes2^(n-1-0) = 2^(2-1-0) = 2^1 = 2
for each row, totaling2 * 3 = 6
. - The second column, we consider flipped (for scoring purposes), so it effectively has 2
1
s, and each contributes2^(n-2-0) = 2^(2-2-0) = 2^0 = 1
to the score. The total from this column will be1 * 2 = 2
.
- The first column, having all
-
The total score is then the sum of the contributions from step 4:
- Total score = Score from column 1 + Score from column 2
- Total score = 6 + 2
- Total score = 8
The highest possible score for the given matrix after the optimal sequence of moves is 8.
Solution Implementation
1class Solution:
2 def matrixScore(self, grid: List[List[int]]) -> int:
3 # Get the number of rows (m) and columns (n) in the grid
4 num_rows, num_cols = len(grid), len(grid[0])
5
6 # Flip the rows where the first element is 0
7 for i in range(num_rows):
8 if grid[i][0] == 0:
9 for j in range(num_cols):
10 # XOR operation to flip the bits (0 becomes 1, and 1 becomes 0)
11 grid[i][j] ^= 1
12
13 # Initialize the variable to store the result
14 result = 0
15
16 # Iterate over columns
17 for j in range(num_cols):
18 # Count the number of 1s in the current column
19 num_ones = sum(grid[i][j] for i in range(num_rows))
20 # Maximize the column value by flipping if necessary (the majority should be 1s)
21 # Use the maximum of the number of 1s or the number of 0s in the column
22 max_value = max(num_ones, num_rows - num_ones)
23
24 # Add the value of the column to the result
25 # The value is determined by the number of 1s times the value of the bit
26 # position (1 << (num_cols - j - 1)) is the bit value of the current column
27 result += max_value * (1 << (num_cols - j - 1))
28
29 # Return the maximized score after considering all rows and columns
30 return result
31
1class Solution {
2 public int matrixScore(int[][] grid) {
3 // Get the number of rows (m) and columns (n) in the grid.
4 int numRows = grid.length, numCols = grid[0].length;
5
6 // Step 1: Flip the rows where the first element is 0.
7 for (int row = 0; row < numRows; ++row) {
8 // Check if the first column of the current row is 0.
9 if (grid[row][0] == 0) {
10 // Flip the entire row.
11 for (int col = 0; col < numCols; ++col) {
12 grid[row][col] ^= 1; // Bitwise XOR operation flips the bit.
13 }
14 }
15 }
16
17 // Step 2: Calculate the final score after maximizing the columns.
18 int ans = 0; // This variable stores the final score.
19
20 // Loop through each column.
21 for (int col = 0; col < numCols; ++col) {
22 int colCount = 0; // Count the number of 1s in the current column.
23 for (int row = 0; row < numRows; ++row) {
24 // Add to the column count if the bit is 1.
25 colCount += grid[row][col];
26 }
27 // Maximize the column by choosing the maximum between colCount and (numRows - colCount).
28 // Use bit shifting (1 << (numCols - col - 1)) to represent the value of the column.
29 ans += Math.max(colCount, numRows - colCount) * (1 << (numCols - col - 1));
30 }
31
32 // Return the final score of the binary matrix after row and column manipulations.
33 return ans;
34 }
35}
36
1class Solution {
2public:
3 int matrixScore(vector<vector<int>>& A) {
4 // Number of rows in the matrix
5 int num_rows = A.size();
6 // Number of columns in the matrix
7 int num_cols = A[0].size();
8
9 // Flip the rows where the first element is 0 to maximize the leading digit
10 for (int row = 0; row < num_rows; ++row) {
11 if (A[row][0] == 0) {
12 for (int col = 0; col < num_cols; ++col) {
13 A[row][col] ^= 1; // Xor with 1 will flip 0s to 1s and vice versa
14 }
15 }
16 }
17
18 int total_score = 0;
19 // Iterate through columns to maximize the score
20 for (int col = 0; col < num_cols; ++col) {
21 int col_count = 0; // Count of 1s in the current column
22
23 // Count the number of 1s in the current column
24 for (int row = 0; row < num_rows; ++row) {
25 col_count += A[row][col];
26 }
27
28 // Determine the value to add to the score for this column
29 // We take the larger number between 'col_count' and 'num_rows - col_count'
30 // to maximize the column value (since either all 1s or all 0s since we can flip)
31 int max_col_value = std::max(col_count, num_rows - col_count);
32 // The value of a set bit in the answer is equal to 2^(num_cols - col - 1)
33 total_score += max_col_value * (1 << (num_cols - col - 1));
34 }
35
36 return total_score; // Return the maximized score after performing the operations
37 }
38};
39
1function matrixScore(grid: number[][]): number {
2 const rows = grid.length; // number of rows in the grid
3 const cols = grid[0].length; // number of columns in the grid
4
5 // Step 1: Toggle rows to ensure the first column has all 1s
6 for (let row = 0; row < rows; ++row) {
7 if (grid[row][0] === 0) {
8 // If the first cell is 0, toggle the entire row
9 for (let col = 0; col < cols; ++col) {
10 grid[row][col] ^= 1; // XOR with 1 will toggle the bit
11 }
12 }
13 }
14
15 let score = 0; // Initialize the total score
16
17 // Step 2: Maximize each column by toggling if necessary
18 for (let col = 0; col < cols; ++col) {
19 let countOnes = 0; // Count of ones in the current column
20 for (let row = 0; row < rows; ++row) {
21 // Count how many 1s are there in the current column
22 countOnes += grid[row][col];
23 }
24 // Choose the max between countOnes and the number of 0s (which is rows - countOnes)
25 score += Math.max(countOnes, rows - countOnes) * (1 << (cols - col - 1));
26 }
27
28 return score; // Return the total score
29}
30
Time and Space Complexity
Time Complexity
The time complexity of the given solution involves iterating over each cell of the grid to potentially toggle its value, followed by counting the number of 1's in each column to maximize the row score.
-
The first loop, which toggles the cells if the leftmost bit is 0, traverses all cells in the grid and performs a constant-time XOR operation. This double loop runs in
O(m * n)
time, wherem
is the number of rows andn
is the number of columns. -
The second loop calculates the count of 1's in each column and determines the maximum score by considering the current and the inverse value count. This also runs in
O(m * n)
time since it involves iterating over each column for all rows.
The two operations above are consecutive, resulting in a total time complexity of O(m * n) + O(m * n)
, which simplifies to O(m * n)
because constant factors are dropped.
Space Complexity
The space complexity of the algorithm is determined by any additional space that we use relative to the input size:
-
No extra space is used for processing besides a few variables for iteration (
i
,j
) and storing intermediate results (such ascnt
andans
). These use a constant amount of space irrespective of the input size. -
Since the grid is modified in place, and no additional data structures are used to store intermediate results, the space complexity remains constant.
Given the fixed number of variables with space independent of the input size, the space complexity is O(1)
, which signifies constant space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following array represent a max heap?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.