Problem

You are given an m x n binary matrix matrix.

You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from 0 to 1 or vice versa).

Return the maximum number of rows that have all values equal after some number of flips.

Examples

Example 1:

1
2
3

Input: matrix = [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.

Example 2:

1
2
3

Input: matrix = [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.

Example 3:

1
2
3

Input: matrix = [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.

Solution

Method 1 - Using a map

Our goal is to maximize the number of rows that have all values equal (either all 0s or all 1s) after we perform some column flips.

Flipping a column means reversing the values in that column (turning 0s into 1s and 1s into 0s).

We notice that after flipping certain columns, each row can turn into another row seen somewhere in the matrix simply by flipping some columns. That means two rows can become the same (i.e., all 1s or all 0s) by performing identical column flips.

So, our key insight is that if two rows can be made identical by some set of flips, one must be the complement of the other. Thus, if we have a known row and its complement, we can use this to determine the maximum number of all equal rows that can be achieved.

We can count the rows using a map (or dictionary) where each key is a row or its flipped equivalent, and the value is the count. The maximum count in this dictionary will give us the maximum number of rows that can be all the same.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        Map<String, Integer> rowCount = new HashMap<>();
        for (int[] row : matrix) {
            StringBuilder sb = new StringBuilder();
            StringBuilder flippedSb = new StringBuilder();
            for (int cell : row) {
                sb.append(cell);
                flippedSb.append(cell ^ 1);  // flip the cell
            }
            String str = sb.toString();
            String flippedStr = flippedSb.toString();
            rowCount.put(str, rowCount.getOrDefault(str, 0) + 1);
            rowCount.put(flippedStr, rowCount.getOrDefault(flippedStr, 0) + 1);
        }
        int ans = 0;
        for (int count : rowCount.values()) {
            ans = Math.max(ans, count);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        row_count: defaultdict[str, int] = defaultdict(int)
        for row in matrix:
            str_row = ''.join(map(str, row))
            flipped_row = ''.join(map(str, [1 - x for x in row]))
            row_count[str_row] += 1
            row_count[flipped_row] += 1
            
        ans: int = max(row_count.values())
        return ans

Complexity

  • ⏰ Time complexity: O(m * n) - where m is the number of rows and n is the number of columns, since we traverse each cell in the matrix once.
  • 🧺 Space complexity: O(m) - for the dictionary storing up to m rows.