Problem statement

https://leetcode.com/problems/score-after-flipping-matrix/

Solution

The idea here, when we can flip matrix in given way, that it will always be uniquely defined by its left column and top row, that is for any given values of these m + n - 1 elements, we can reconstruct the rest of the matrix: we have property that for every rectangle sum of corners will always be the fixed after any flipping of matrix.

Here we need to make left column equal to all ones, after these we can flip only other columns. For each of other columns, we found how many ones we have there and decide to flip it or not.

Complexity

Time complexity is O(mn), space is O(1).

Code

class Solution:
    def matrixScore(self, A):
        m, n = len(A), len(A[0])
        ans = (1<<(n-1))*m
        
        for j in range(1, n):
            cand = sum(A[i][0]^A[i][j] for i in range(m))
            ans += max(cand, m - cand)*1<<(n-1-j)
        
        return ans