Code Implementation

from collections import Counter
from typing import List

class Solution:
    def maxEqualRowsAfterFlips(self, matrix: List[List[int]]) -> int:
        patterns = Counter()
        for row in matrix:
            # Normalize: flip the row if the first element is 1
            # So all rows start with 0 (by flipping columns as needed)
            first = row[0]
            normalized = tuple(x ^ first for x in row)
            patterns[normalized] += 1
        return max(patterns.values())
      

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        unordered_map<string, int> patterns;
        for (auto& row : matrix) {
            string pattern;
            int first = row[0];
            for (int x : row) {
                pattern += (x ^ first) + '0';
            }
            patterns[pattern]++;
        }
        int res = 0;
        for (auto& p : patterns) {
            res = max(res, p.second);
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        Map<String, Integer> patterns = new HashMap<>();
        for (int[] row : matrix) {
            int first = row[0];
            StringBuilder sb = new StringBuilder();
            for (int x : row) {
                sb.append(x ^ first);
            }
            String key = sb.toString();
            patterns.put(key, patterns.getOrDefault(key, 0) + 1);
        }
        int res = 0;
        for (int count : patterns.values()) {
            res = Math.max(res, count);
        }
        return res;
    }
}
      

/**
 * @param {number[][]} matrix
 * @return {number}
 */
var maxEqualRowsAfterFlips = function(matrix) {
    let patterns = new Map();
    for (let row of matrix) {
        let first = row[0];
        let norm = row.map(x => x ^ first).join(',');
        patterns.set(norm, (patterns.get(norm) || 0) + 1);
    }
    let res = 0;
    for (let count of patterns.values()) {
        res = Math.max(res, count);
    }
    return res;
};
      

Problem Description

• Each flip inverts all bits in a column (0 to 1 and 1 to 0).
• You may flip any subset of columns, and each column can be flipped at most once (since flipping twice is the same as not flipping).
• You do not flip rows, only columns.
• Constraints:
  • 1 <= matrix.length, matrix[0].length <= 300
  • Each element of matrix is 0 or 1.

Thought Process

Solution Approach

1. Normalize each row: For each row, create a normalized pattern by XOR-ing every element in the row with the first element of that row. This means:
   • If the first element is 0, the row is unchanged.
   • If the first element is 1, every bit in the row is flipped (since 1 XOR x flips x).
   This ensures that any row that can be made all-zeros (by flipping columns) will have the same normalized pattern.
2. Count patterns: Use a hash map (dictionary) to count how many times each normalized pattern appears. Each pattern represents a group of rows that can be made identical by flipping the same set of columns.
3. Find the maximum: The answer is the largest count among all patterns in the hash map. This is the maximum number of rows that can be made equal via some column flips.

We use a hash map because it allows O(1) time insertion and lookup for each pattern, making the solution efficient.

Example Walkthrough

Suppose matrix = [[0,1],[1,0],[1,1]].

1. First row: [0,1]
   • First element is 0, so normalized row is [0,1]
2. Second row: [1,0]
   • First element is 1, so normalize by XOR with 1: [1^1, 0^1] = [0,1]
3. Third row: [1,1]
   • First element is 1, normalize: [1^1, 1^1] = [0,0]

Now, our patterns are:

• [0,1] appears twice
• [0,0] appears once

Time and Space Complexity

• Brute-force approach: Would require checking all 2^n column flips, and for each, comparing all rows. This is O(2^n * m * n), which is infeasible for n up to 300.
• Optimized approach:
  • We process each row once, and for each row, we perform O(n) normalization work.
  • We use a hash map to store up to m patterns.
  • Total time complexity: O(m * n)
  • Space complexity: O(m * n) for storing the patterns.

Summary

The key insight is that, rather than examining every possible set of column flips, we can "normalize" each row so that all rows that could be made equal by flipping columns will have the same normalized pattern. By counting the frequency of each pattern, we efficiently determine the largest group of rows that can be made identical. This approach is both elegant and efficient, reducing the problem from exponential to linear time with respect to the matrix size.