Problem Breakdown
We are given an binary matrix. The goal is to flip any number of columns (changing all bits in that column from 0 to 1 or vice versa) such that the maximum number of rows become uniform (all values equal). A row becomes uniform if it consists entirely of 0s or entirely of 1s after flips.
Inputs:
matrix: An list of lists containing integers 0 and 1.
Outputs:
- Integer: The maximum count of rows that can be made uniform simultaneously.
Constraints & Edge Cases:
- Matrix dimensions up to . This allows for an algorithm with time complexity around .
- Values are strictly binary (
0or1). - Rows must become all
0s OR all1s. It does not matter which state they end in, as long as the row is uniform.
Intuition
Flipping a column affects every row at that specific index simultaneously. If we have two rows that are identical (e.g., [0, 1] and [0, 1]), any set of column flips applied to make one uniform will apply identically to the other. Thus, they belong to the same equivalence class.
If we have two inverse rows (e.g., [0, 1] and [1, 0]), flipping all columns that correspond to 1s in the first row effectively transforms both into a state where one is uniform or vice versa relative to each other. Specifically, if Row A becomes all 0s after flips, its inverse (Row B) will become all 1s. Both are considered “uniform”.
Key Insight:
Two rows can be made uniform simultaneously if and only if they are either identical bitwise OR inverses of each other. We do not need to track which specific flip pattern is used; we just need to group compatible rows together. To simplify grouping, we normalize every row so that it always starts with a 0. If the first element is 1, we invert all bits in that row (conceptually) and use this inverted version as a canonical key for our hash map. This merges identical rows and inverse rows into the same bucket.
Approach
- Initialize an empty frequency dictionary (
counts) to store how many times each normalized pattern appears. - Iterate through each row in the matrix:
- Check the first element of the current row (index
0). - If it is
0, use the tuple representation of the row directly as the key for our dictionary. This represents rows that are already “aligned” to start with a zero. - If it is
1, invert all bits in the row () and use this inverted tuple as the key. For example,[1, 0]becomes(0, 1)which matches the canonical form of an identical row starting with0. - Increment the count for this specific normalized key.
- Check the first element of the current row (index
- After processing all rows, return the maximum value found in our frequency dictionary. If no keys exist (empty matrix), handle gracefully by returning 0.
Complexity Analysis
- Time Complexity: , where is number of rows and is columns. We iterate through each cell exactly once to construct the tuple key for hashing. Hashing a tuple takes time proportional to its length (), so total work per row is linear in width.
- Space Complexity: In the worst case, we store up to unique keys of length . Thus, space complexity is bounded by . Given constraints (), this fits well within memory limits.
Solution
from collections import defaultdict
def maxEqualRowsAfterFlips(matrix):
counts = defaultdict(int)
for row in matrix:
# Normalize the row so that it always starts with a 0.
# If the first element is 1, flip all bits to create a canonical key
# representing this equivalence class (identical or inverse rows).
if row[0] == 1:
# Create inverted tuple for hashing
counts[tuple(1 - x for x in row)] += 1
else:
# Use original tuple as hashable key
counts[tuple(row)] += 1
return max(counts.values()) if counts else 0
# Example usage / Test cases from problem description
if __name__ == "__main__":
print(maxEqualRowsAfterFlips([[0,1],[1,1]])) # Output: 1
print(maxEqualRowsAfterFlips([[0,1],[1,0]])) # Output: 2
print(maxEqualRowsAfterFlips([[0,0,0],[0,0,1],[1,1,0]])) # Output: 2
Edge Cases Handled
- Single Row/Column: The logic holds regardless of dimensions; a single row is always uniform after appropriate flips (count = 1).
- All Identical Rows: All map to the same key without inversion. Count equals .
- Inverse Pairs Only: E.g.,
[[0,1], [1,0]]. First maps to(0,1), second inverts to(0,1). Both increment same bucket. Max count = 2. - Empty Matrix (Hypothetical): The code checks if the dictionary is empty before calling max(), returning 0 safely, though constraints prevent this input ().