LeetCode Entry
1072. Flip Columns For Maximum Number of Equal Rows
Max same-bit-rows after flipping columns in 01-2D matrix
1072. Flip Columns For Maximum Number of Equal Rows medium
blog post
substack
youtube
deep-dive
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/808
Problem TLDR
Max same-bit-rows after flipping columns in 01-2D matrix #medium #matrix
Intuition
Let’s observe what’s happening:
// 0 0 0 ---
// 0 0 1 ff- or --f <-- mask
// 1 1 0 ff- or --f
// 1 1 1 ---
// v
// 0 0 1
// 0 0 0
// 1 1 1
// 1 1 0
// *
//
// 0 1 0
// 0 1 1
// 1 0 0
// 1 0 1
// * <-- intermediate column flips are irrelevant
// 0 0 0 0 0 *
// 1 1 1 1 1 *
// 0 0 0 0 1 *
// 1 1 1 1 0 *
// 0 0 0 1 1 * <-- symmetry
// 1 1 1 0 0 * <-- symmetry
// 0 0 1 1 1 *
// 1 1 0 0 0 *
// 0 1 1 1 1 *
// 1 0 0 0 0 *
Some observations:
- intermediate flips are irrelevant, only pattern-flips can improve the situation
- each row has a pattern and this pattern has a symmetry with its inverted version
- the pattern and its inversion forms a groups, group size is the answer
Approach
- one trick to collapse pattern with its inversion is to xor each with the first bit (@lee’s brain idea)
- in Kotlin, simple groupBy works faster than strings hashes
- in Rust [u8] key is faster than
[u128, u128, u128], or[u64; 5]keys - c++ has bitset built-in
Complexity
-
Time complexity: \(O(nm)\)
-
Space complexity: \(O(nm)\)
Code
fun maxEqualRowsAfterFlips(matrix: Array<IntArray>) =
matrix.groupBy { r -> r.map { it xor r[0] }}
.maxOf { it.value.size }
pub fn max_equal_rows_after_flips(matrix: Vec<Vec<i32>>) -> i32 {
*matrix.iter().fold(HashMap::new(), |mut hm, r| {
*hm.entry(r.iter().map(|&b| r[0] ^ b).collect::<Vec<_>>())
.or_insert(0) += 1; hm
}).values().max().unwrap() as i32
}
int maxEqualRowsAfterFlips(vector<vector<int>>& m) {
unordered_map<bitset<300>, int>c; int r = 0;
for (auto v: m) {
bitset<300>b;
for (int i = 0; i < size(v);) b[i] = v[0] ^ v[i++];
r = max(r, ++c[b]);
}
return r;
}