# Flip Columns For Maximum Number of Equal Rows
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/flip-columns-for-maximum-number-of-equal-rows)
Canonical: https://scaleengineer.com/dsa/problems/flip-columns-for-maximum-number-of-equal-rows
**Data structures:** Array, Hash Table, Matrix
---
## Problem
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`.

# Approaches
## Brute-force Comparison of Rows
This approach iterates through each row of the matrix, considering it as a reference pattern. For each reference row, it then compares it against every other row in the matrix to count how many can be made uniform (all 0s or all 1s) with the same set of column flips.
**Time:** O(m² * n), where `m` is the number of rows and `n` is the number of columns. The three nested loops (two for rows, one for columns) lead to this complexity. · **Space:** O(1). The algorithm uses only a constant amount of extra space for variables like counters and flags.
**Pros:** Simple to understand and implement.; Low memory overhead as it doesn't require complex data structures.
**Cons:** Inefficient due to its cubic time complexity.; Likely to result in a 'Time Limit Exceeded' error for larger inputs (e.g., m, n > 100).
### Explanation
The fundamental insight is that for a group of rows to become all-equal after some column flips, they must all conform to the same pattern or its exact inverse (complement). For instance, if we decide to make `row i` all zeros, the required flips are determined: we must flip every column `j` where `matrix[i][j]` is `1`. Any other `row k` can also be made uniform (either all zeros or all ones) by this same set of flips if and only if `row k` is identical to `row i` or `row k` is the complement of `row i`.

This method systematically checks this condition. It picks each row `i` as a reference and then iterates through all rows `j` (including `i` itself), performing a direct, element-by-element comparison to see if `row j` is identical to `row i` or is its complement. The maximum count found across all reference rows is the answer.

```java
class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;

        for (int i = 0; i < m; i++) {
            int count = 0;
            for (int j = 0; j < m; j++) {
                boolean identical = true;
                boolean complement = true;
                for (int k = 0; k < n; k++) {
                    if (matrix[i][k] != matrix[j][k]) {
                        identical = false;
                    }
                    if (matrix[i][k] == matrix[j][k]) {
                        complement = false;
                    }
                }
                if (identical || complement) {
                    count++;
                }
            }
            if (count > max) {
                max = count;
            }
        }
        return max;
    }
}
```
### Algorithm
- Initialize a variable `max_rows` to 0.
- Iterate through each row `i` from `0` to `m-1` to use as a reference pattern.
- For each `row i`, initialize a `current_count` to 0.
- Iterate through every row `j` from `0` to `m-1` to compare against the reference.
- For each pair of rows `(i, j)`, check if they are identical or complements by comparing them element by element over all `n` columns.
- If `row j` is identical to or a complement of `row i`, increment `current_count`.
- After checking `row i` against all other rows, update `max_rows = max(max_rows, current_count)`.
- After iterating through all possible reference rows, return `max_rows`.

## Hashing Canonical Row Patterns
This optimized approach avoids redundant comparisons by grouping rows that can be made uniform together. It recognizes that all rows that are either identical or complements of each other belong to the same group. By converting each row to a canonical form and using a hash map to count the frequency of each form, we can find the size of the largest group in linear time relative to the matrix size.
**Time:** O(m * n), where `m` is the number of rows and `n` is the number of columns. We iterate through each of the `m` rows, and for each row, we perform O(n) work to build the string key. · **Space:** O(m * n) in the worst case. If all `m` rows have unique canonical patterns, the hash map will store `m` keys, each of length `n`.
**Pros:** Optimal time complexity, solving the problem efficiently.; Scales well with the size of the input matrix.
**Cons:** Requires additional space for the hash map, which can be up to O(m * n) in the worst case.
### Explanation
The core idea is to map every row to a canonical representation. For any row, it and its complement form a pair that can be made uniform by the same set of flips. For example, `[0, 1, 1]` and its complement `[1, 0, 0]` belong to the same group. We can choose one of these as the 'canonical' pattern for the group. A simple and effective rule is to always pick the pattern that starts with a `0`.

If a row already starts with `0`, it's its own canonical form. If it starts with `1`, its complement (which will start with `0`) is the canonical form. This normalization can be achieved efficiently by XORing every element of a row with its first element.

We iterate through the matrix, compute the canonical string representation for each row, and use a hash map to count how many rows map to the same canonical string. The maximum count found in the hash map is the answer.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int maxEqualRowsAfterFlips(int[][] matrix) {
        Map<String, Integer> patternCount = new HashMap<>();
        int n = matrix[0].length;

        for (int[] row : matrix) {
            StringBuilder sb = new StringBuilder();
            int firstElement = row[0];
            for (int j = 0; j < n; j++) {
                // Normalize the row by XORing with the first element.
                // This ensures the canonical pattern always starts with '0'.
                sb.append(row[j] ^ firstElement);
            }
            String key = sb.toString();
            patternCount.put(key, patternCount.getOrDefault(key, 0) + 1);
        }

        int max = 0;
        for (int count : patternCount.values()) {
            if (count > max) {
                max = count;
            }
        }

        return max;
    }
}
```
### Algorithm
- Initialize a `HashMap<String, Integer>` to store the frequency of each canonical row pattern.
- Iterate through each `row` in the input `matrix`.
- For each `row`, create its canonical representation:
  - If the first element `row[0]` is `1`, the canonical pattern is the complement of the row.
  - If the first element `row[0]` is `0`, the canonical pattern is the row itself.
  - A simple way to do this is to create a new pattern where each element is `row[j] ^ row[0]`.
- Convert this canonical pattern array into a `String` to be used as a key in the hash map.
- Increment the count for this key in the map.
- After processing all rows, iterate through the values of the hash map to find the maximum frequency.
- Return this maximum frequency.

# Solutions
### Java

```java
class Solution { public int maxEqualRowsAfterFlips ( int [][] matrix ) { Map < String , Integer > cnt = new HashMap <>(); int ans = 0 , n = matrix [ 0 ]. length ; for ( var row : matrix ) { char [] cs = new char [ n ]; for ( int i = 0 ; i < n ; ++ i ) { cs [ i ] = ( char ) ( row [ 0 ] ^ row [ i ]); } ans = Math . max ( ans , cnt . merge ( String . valueOf ( cs ), 1 , Integer: : sum )); } return ans ; } }
```

### CPP

```cpp
class Solution { public: int maxEqualRowsAfterFlips ( vector < vector < int >>& matrix ) { unordered_map < string , int > cnt ; int ans = 0 ; for ( auto & row : matrix ) { string s ; for ( int x : row ) { s . push_back ( '0' + ( row [ 0 ] == 0 ? x : x ^ 1 )); } ans = max ( ans , ++ cnt [ s ]); } return ans ; } };
```

### Python

```python
class Solution : def maxEqualRowsAfterFlips ( self , matrix : List [ List [ int ]]) -> int : cnt = Counter () for row in matrix : t = tuple ( row ) if row [ 0 ] == 0 else tuple ( x ^ 1 for x in row ) cnt [ t ] += 1 return max ( cnt . values ())
```