LC861. Score After Flipping Matrix

Approach 1: $O(m\cdot n)$

class Solution:
    def matrixScore(self, grid: List[List[int]]) -> int:
        nrows, ncols = len(grid), len(grid[0])
 
        # Score can only be maximized if significant bit is 1
        # Even if rest of the bits flip to 0, the resulting value
        # is still higher than if the MSB was 0.
        for r in range(nrows):
            if grid[r][0] == 0:
                for c in range(ncols):
                    grid[r][c] ^= 1
        
        # For columns, we flip bits only if num_zeroes > num_ones. Doesn't
        # matter which row's columns are flipped if condition is met as the
        # flipped zeroes will make up for the flipped ones.
        for c in range(ncols):
            one_count = sum(grid[r][c] for r in range(nrows))
            zero_count = nrows - one_count
 
            if zero_count > one_count:
                for r in range(nrows):
                    grid[r][c] ^= 1
        
        # Calculate the sum of binary numbers in rows
        total = 0
        for r in range(nrows):
            num = 0
            for c in range(ncols):
                num += grid[r][c] << (ncols - c - 1)
            total += num
 
        return total

Complexity

Time: $O(m\cdot n)$
Space: $O(1)$

Notes

Other Languages