Leetcode 1072: Flip Columns For Maximum Number of Equal Rows

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.

Problem Analysis:

If we iterate all possibilities, the time complexity is O(m x 2^n). For each column, we make a flip or not, and then compare with the next column.

So we need to optimize it. For simplicity, assume there is a matrix only have two columns. We choose the ith row, if row[i][1] != row[i][0], we can flip the second column to make row[i][1] == row[i][0].

So for every row i, if row[i][1] != row[i][0], after flips, the ith row has the equal values. Also if row[i][1]=row[i][0], we don’t need to flip. In other words, if we don’t flip, the rows that have the same values are those which row[i][1]=row[i][0], or if we flip the second column, the rows that have the same values are those which row[i][1] != row[i][0].

So for matrix has more columns, we can also compare the column with the first column to make row[i][j]=row[i][0], as we can flip or not flip the jth column.

So we have a solution that make every column compare the first column, then we get the relationships, and rows that have the same relationships can have the equal values after some flips.

Solution

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        unordered_map<string, int> strs;
        for (const auto& item: matrix) {
            string s;
            for (int i = 1; i < item.size(); ++i) {
                if (item[i] == item[0]) s += '1';
                else s += '0';
            }
            ++strs[s];
        }

        int res{0};
        for (const auto& [_, value]: strs) res = max(res, value);

        return res;
    }
};

Time complexity is O(mn)

Space complexity is O(mn)