861. Score After Flipping Matrix

Approach 1: Brute Force

One thing note was that trying all combinations was crazy stupid, since it is a runtime of 2^(M*N) so there was a way that we had to optimize

Approach 2: Greedy Solution

class Solution(object):
    def matrixScore(self, A):
        """
        https://leetcode.com/problems/score-after-flipping-matrix/description/
        :type A: List[List[int]]
        :rtype: int
        """
        R, C = len(A), len(A[0])
        ans = 0
        for c in range(C):
            col = 0
            for r in range(R):
                col += A[r][c] ^ A[r][0]
            ans += max(col, R - col) * (1 << (C - 1 - c))
        return ans

This one took a while. Making the most significant bit one will give the highest return since if those are one then we can get a sum of at least R * 2^(C-1). Once we have decided to toggle all of those to be one, we have to iterate through all of the other columns to decide which ones to toggle based on the number of ones that they have, and toggle only if they have less ones than zeroes

An optimized way to do this would be XOR all the columns with the first column and decide which ones to toggle based on their counts of ones.

Calculating the end sum can be optimized even further by using bit shifting since we have to calculate a power of 2

Time Complexity: O(R*C) where R and C are the dimensions of the matrix

Space Complexity: O(1)