Score After Flipping Matrix — LeetCode 861 Python Solution

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).

Example

Input

grid = [[0,0,1,1],[1,0,1,0],[1,1,0,0]]

Output

39

Explanation

0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

Python solution

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        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
        ans = 0
        for j in range(n):
            cnt = sum(grid[i][j] for i in range(m))
            ans += max(cnt, m - cnt) * (1 << (n - j - 1))
        return ans

Complexity

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 861. Score After Flipping Matrix is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems