Score After Flipping Matrix - Leetcode Solution

Problem:

We have a two-dimensional matrix A where each value is 0 or 1.

A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.

After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.

Return the highest possible score.

Example:

Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]

Output: 39

Explanation:

Toggled [0,0,1,1] to [1,1,0,0], and toggled [1,0,1,0] to [0,1,0,1].

After these moves, the matrix is [[1,1,0,0],[0,1,0,1],[1,1,0,0]].

This is a binary matrix so its row scores are 12, 5, and 12.

The total score is 12 + 5 + 12 = 29.

Constraints:

1 <= A.length <= 20

1 <= A[0].length <= 20

A[i][j] is 0 or 1.

Solution:

The crux of the solution is to find the optimal sequence of toggling rows and columns that will give us the maximum score.

To do this, we first make sure that the leftmost column of the matrix has all 1s. This can be achieved by toggling each row where the leftmost cell is 0.

Next, we want to maximize the score of each row. We can achieve this by toggling columns in such a way that each row has the maximum number of cells with 1. Specifically, if a row has more 0s than 1s, we toggle the columns where that row has a 0. After doing this for every row, we now have a matrix where every row has its maximum score.

Finally, we calculate the total score of the matrix by adding up the scores of each row.

Here is the Python code that implements this solution:

class Solution: def matrixScore(self, A: List[List[int]]) -> int: m, n = len(A), len(A[0]) # toggle rows so that the leftmost column has all 1s for i in range(m): if A[i][0] == 0: for j in range(n): A[i][j] ^= 1 # toggle columns to maximize the score of each row for j in range(1, n): count = sum(A[i][j] for i in range(m)) if count * 2 < m: for i in range(m): A[i][j] ^= 1 # compute the total score score = 0 for i in range(m): score += int(''.join(map(str, A[i])), 2) return score

The time complexity of this solution is O(m*n), where m and n are the dimensions of the matrix. The space complexity is O(1), since we are modifying the input matrix in-place.

1