Flip Columns For Maximum Number of Equal Rows

medium hash map matrix counting

Problem

You are given an m x n binary matrix. You may choose any number of columns and flip every cell in those columns (turning 0 into 1 and 1 into 0). Return the maximum number of rows that can be made to have all values equal after some sequence of flips.

Inputmatrix = [[0,0,0],[0,0,1],[1,1,0]]

Output2

Flip no columns: rows [0,0,0] and [1,1,0] are not yet equal. But two rows share the same flip pattern — see below — so 2 rows can become all-equal at once.

matrix (rows separated by ; values by ,)

def max_equal_rows_after_flips(matrix):
    count = {}
    best = 0
    for row in matrix:
        first = row[0]
        key = tuple(c ^ first for c in row)
        count[key] = count.get(key, 0) + 1
        best = max(best, count[key])
    return best

function maxEqualRowsAfterFlips(matrix) {
  const count = new Map();
  let best = 0;
  for (const row of matrix) {
    const first = row[0];
    const key = row.map(c => c ^ first).join(",");
    const next = (count.get(key) || 0) + 1;
    count.set(key, next);
    best = Math.max(best, next);
  }
  return best;
}

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

int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
    unordered_map<string, int> count;
    int best = 0;
    for (auto& row : matrix) {
        int first = row[0];
        string key;
        for (int c : row) key += ('0' + (c ^ first));
        best = max(best, ++count[key]);
    }
    return best;
}

Explanation

The key insight is that two rows can be made identical by flipping columns if and only if they are already the same or are exact opposites of each other. Flipping a column toggles that bit in every row at once, so rows that move "in lockstep" stay matched.

To detect both cases with one key, we normalize each row by XOR-ing every cell with the row's first cell: key = tuple(c ^ first for c in row). This forces every normalized row to start with 0, so a row and its complement collapse to the same signature.

We feed each normalized key into a hash map that counts how many rows share it, tracking the largest count in best as we go.

Example: rows [0,0,0] and [1,1,1] both normalize to [0,0,0] (the second one XORs each cell with its leading 1). They land in the same bucket, so that pattern's count is 2.

The answer is the size of the most populated bucket, since those rows can all be flipped into agreement simultaneously.

Time: O(m · n) Space: O(m · n)