Flip Columns For Maximum Number of Equal Rows - Solution & Explanation

Problem Overview: You are given a binary matrix. You can flip any column (change 0 → 1 and 1 → 0 for that column). The goal is to maximize the number of rows that become identical after any number of column flips.

The key observation: two rows can become equal if one row is exactly the same as the other, or if it is the complete inverse of the other. Flipping columns globally affects every row, so rows that share the same relative pattern will align after the same column operations.

Approach 1: Row Pattern Matching using HashMap (Time: O(m*n), Space: O(m*n))

Iterate through each row and convert it into a canonical pattern. If the first element of a row is 1, flip the entire logical representation of the row while building the pattern. This normalizes rows and their inverses into the same representation. Store the normalized pattern as a string or tuple in a hash map and count its frequency. Rows that map to the same pattern can all become identical after flipping the same set of columns. The maximum frequency in the hash map is the answer.

This works because column flips affect every row equally. Normalizing rows relative to the first element groups rows that differ only by a global column flip configuration. Hash lookups provide constant-time aggregation of identical patterns.

Approach 2: Row Pattern Counting with Initial Flip Consideration (Time: O(m*n), Space: O(m*n))

Another way to think about the same idea is to explicitly consider both the original row and its inverted form. For each row, build two patterns: the row itself and the row with all bits flipped. Insert both patterns into a frequency map and count how many rows can match either configuration. Rows that are complements of each other become identical once the correct columns are flipped.

This method is conceptually straightforward and highlights the symmetry between rows and their complements. However, it performs slightly more work per row because both patterns are generated.

The solution relies heavily on pattern grouping using a hash table. The matrix traversal is a simple nested loop over rows and columns using basic array operations, and the data structure being processed is a binary matrix.

Recommended for interviews: The row normalization hash map approach is what most interviewers expect. It demonstrates that you noticed the core invariant: rows and their complements behave the same under column flips. A brute-force simulation of flips would explode combinatorially, while the hash-based pattern grouping keeps the complexity linear in the size of the matrix.