1072

1072. Flip Columns For Maximum Number of Equal Rows (Medium)

You are given an m x n binary matrix matrix.

You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from 0 to 1 or vice versa).

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

 

Example 1:

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

Example 2:

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

Example 3:

Input: matrix = [[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.

 

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is either 0 or 1.

Related Topics:
Array, Hash Table, Matrix

Solution 1.

Intuition: If two rows a and b can be flipped to be equal, either a == b or a == ~b. So we can:

1. For each row, if the first element is not 0, flip the row.
2. Find the maximum count of the rows having the same content.

// OJ: https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& A) {
        int N = A[0].size(), ans = 0;
        unordered_map<string, int> cnt;
        for (auto &row : A) {
            bool flip = row[0] == 0;
            string s;
            for (int i = 0; i < N; ++i) s += '0' + (row[i] ^ flip);
            ans = max(ans, ++cnt[s]);
        }
        return ans;
    }
};