Problem statement

https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/

Solution

First of all every position is characterized with which columns we flipped. For every row we can make it either all zeroes or ones and it will uniquely get our flips of columns. We can check this for every row and get O(m^2 n) solution. Notice, that if rows were equal, then if we make one of them 0 or 1, then the other also will be 0 or 1. The same is true for pairs of complementary rows, such that 00101 and `11010. So, we calculate for each row how many we have it and its complementary and then choose the maximum value.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def maxEqualRowsAfterFlips(self, M):
        cnt = Counter()
        for row in M:
            if row[0] == 1:
                row = [1 - x for x in row]
            cnt[tuple(row)] += 1
        
        return max(cnt.values())