Flip Columns For Maximum Number of Equal Rows — Solution
Flip Columns For Maximum Number of Equal Rows solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Flip Columns For Maximum Number of Equal Rows is a medium coding problem on arrays, hash table and matrix, asked in Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Matrix
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n binary matrix. You may choose any set of columns and flip every cell in them (each 0 becomes 1 and each 1 becomes 0).
A row is uniform when all of its cells hold the same value. Return the maximum number of rows that can be uniform at the same time after some choice of column flips.
Example 1
Input: matrix = [[0,1],[1,1]]
Output: 1
Explanation: Without flips the second row is already uniform. No choice makes both rows uniform.
Example 2
Input: matrix = [[0,1],[1,0]]
Output: 2
Explanation: Flip the first column: the rows become `[1,1]` and `[0,0]`.
Example 3
Input: matrix = [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: Flip the last column: the rows become `[0,0,1]`, `[0,0,0]` and `[1,1,1]`.
Constraints
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j] is 0 or 1
Hints for Flip Columns For Maximum Number of Equal Rows
Hint 1
Once you fix the set of flipped columns, which rows end up uniform?
Hint 2
Two rows can be uniform together only if they are identical or exact complements of each other.
Hint 3
Normalise each row so it starts with 0 (complement it otherwise) and count the most common normalised row.
How to solve Flip Columns For Maximum Number of Equal Rows
Making a row uniform forces the exact set of columns to flip (up to flipping all of them). So rows that become uniform together share a pattern: they are equal or complementary. Normalising every row to start with 0 maps a row and its complement to the same key.
Approach
- For each row, if its first cell is 1, complement the whole row; otherwise keep it.
- Count identical normalised rows with a hash map (key: the row as a string or tuple).
- Return the largest count.
Why it works
Flipping exactly the columns where a row holds 1 makes it all zeros; the only other uniforming choice is the complementary set. A second row is uniform under the same flips exactly when it equals the first row (it becomes all zeros) or its complement (it becomes all ones). Both cases normalise to the same key, so the most frequent key is the largest set of rows that can be uniform together.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- Counting only identical rows misses complementary rows, which become uniform with the opposite value.
- Build the key from the whole row — comparing only a few cells or summing values conflates different patterns.
Reference solution
Python
from typing import List
from collections import Counter
def maxEqualRowsAfterFlips(matrix: List[List[int]]) -> int:
seen = Counter()
for row in matrix:
key = tuple(v ^ row[0] for v in row)
seen[key] += 1
return max(seen.values())Java
public static int maxEqualRowsAfterFlips(int[][] matrix) {
Map<String, Integer> seen = new HashMap<>();
int best = 0;
for (int[] row : matrix) {
char[] key = new char[row.length];
for (int j = 0; j < row.length; j++) key[j] = (char) ('0' + (row[j] ^ row[0]));
int c = seen.merge(new String(key), 1, Integer::sum);
best = Math.max(best, c);
}
return best;
}C++
int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
unordered_map<string, int> seen;
int best = 0;
for (auto& row : matrix) {
string key(row.size(), '0');
for (size_t j = 0; j < row.size(); j++) key[j] = (char)('0' + (row[j] ^ row[0]));
best = max(best, ++seen[key]);
}
return best;
}JavaScript
var maxEqualRowsAfterFlips = function(matrix) {
var seen = new Map();
var best = 0;
for (var i = 0; i < matrix.length; i++) {
var row = matrix[i];
var key = '';
for (var j = 0; j < row.length; j++) key += (row[j] ^ row[0]);
var c = (seen.get(key) || 0) + 1;
seen.set(key, c);
if (c > best) best = c;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets