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.

Approach 01:

#include <algorithm>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& binaryMatrix) {
        const int numRows = binaryMatrix.size();
        const int numCols = binaryMatrix[0].size();
        int maxEqualRows = 0;
        vector<int> flippedRow(numCols);
        unordered_set<int> processedRows;

        for (int currentRow = 0; currentRow < numRows; ++currentRow) {
            if (processedRows.contains(currentRow))
                continue;

            int rowCount = 0;

            for (int col = 0; col < numCols; ++col)
                flippedRow[col] = 1 ^ binaryMatrix[currentRow][col];

            for (int checkRow = 0; checkRow < numRows; ++checkRow) {
                if (binaryMatrix[checkRow] == binaryMatrix[currentRow] || binaryMatrix[checkRow] == flippedRow) {
                    processedRows.insert(checkRow);
                    ++rowCount;
                }
            }

            maxEqualRows = max(maxEqualRows, rowCount);
        }

        return maxEqualRows;
    }
};

from typing import List

class Solution:
    def maxEqualRowsAfterFlips(self, binaryMatrix: List[List[int]]) -> int:
        numRows = len(binaryMatrix)
        numCols = len(binaryMatrix[0])
        maxEqualRows = 0
        processedRows = set()

        for currentRow in range(numRows):
            if currentRow in processedRows:
                continue

            rowCount = 0
            flippedRow = [1 ^ binaryMatrix[currentRow][col] for col in range(numCols)]

            for checkRow in range(numRows):
                if (binaryMatrix[checkRow] == binaryMatrix[currentRow] or 
                        binaryMatrix[checkRow] == flippedRow):
                    processedRows.add(checkRow)
                    rowCount += 1

            maxEqualRows = max(maxEqualRows, rowCount)

        return maxEqualRows

Time Complexity

• Outer Loop (Over Rows):

  The function iterates over all rows of the matrix, so this loop runs \( O(m) \), where \( m \) is the number of rows in the binary matrix.

• Inner Loop (Comparing Rows):

  For each row in the outer loop, it compares with all rows in the matrix. This nested loop has a complexity of \( O(m \cdot n) \), where \( n \) is the number of columns, because each row comparison involves iterating through all columns.

• Flipping a Row:

  Creating the flipped version of the row takes \( O(n) \), as it involves iterating through the columns.

• Overall Time Complexity:

  Combining these, the overall time complexity is \( O(m^2 \cdot n) \), dominated by the nested loops over rows and columns.

Space Complexity

• Flipped Row:

  The flippedRow vector stores \( n \) elements, where \( n \) is the number of columns. This requires \( O(n) \) space.

• Processed Rows Set:

  The processedRows set can store up to \( m \) elements (one for each row). This requires \( O(m) \) space.

• Input Matrix:

  The input matrix binaryMatrix is given and does not contribute to additional space usage.

• Overall Space Complexity:

  The overall space complexity is \( O(m + n) \), as the set and vector dominate the space usage.