1072. Flip Columns For Maximum Number of Equal Rows

Given a matrix consisting of 0s and 1s, we may choose any number of columns in the matrix and flip every cell in that column.  Flipping a cell changes the value of that cell from 0 to 1 or from 1 to 0.

Return the maximum number of rows that have all values equal after some number of flips.

 

Example 1:

Input: [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.

Example 2:

Input: [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.

Example 3:

Input: [[0,0,0],[0,0,1],[1,1,0]]
Output: 2
Explanation: After flipping values in the first two columns, the last two rows have equal values.

 

Note:

  1. 1 <= matrix.length <= 300
  2. 1 <= matrix[i].length <= 300
  3. All matrix[i].length's are equal
  4. matrix[i][j] is 0 or 1

Rust Solution

struct Solution;

impl Solution {
    fn max_equal_rows_after_flips(matrix: Vec<Vec<i32>>) -> i32 {
        let n = matrix.len();
        let m = matrix[0].len();
        let mut res = vec![1; n];
        for i in 0..n {
            for j in 0..i {
                let count: usize = matrix[i]
                    .iter()
                    .zip(matrix[j].iter())
                    .map(|(x, y)| if x == y { 1 } else { 0 })
                    .sum();
                if count == 0 || count == m {
                    res[i] += 1;
                    res[j] += 1;
                }
            }
        }
        *res.iter().max().unwrap() as i32
    }
}

#[test]
fn test() {
    let matrix = vec_vec_i32![[0, 1], [1, 1]];
    let res = 1;
    assert_eq!(Solution::max_equal_rows_after_flips(matrix), res);
    let matrix = vec_vec_i32![[0, 1], [1, 0]];
    let res = 2;
    assert_eq!(Solution::max_equal_rows_after_flips(matrix), res);
    let matrix = vec_vec_i32![[0, 0, 0], [0, 0, 1], [1, 1, 0]];
    let res = 2;
    assert_eq!(Solution::max_equal_rows_after_flips(matrix), res);
}

Having problems with this solution? Click here to submit an issue on github.