Flip Columns For Maximum Number of Equal Rows

Med

#1021Time: 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.

Data structures

Array Hash Table Matrix

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int maxEqualRowsAfterFlips(int[][] matrix) {3        int m = matrix.length;4        int n = matrix[0].length;5        int max = 0;6 7        for (int i = 0; i < m; i++) {8            int count = 0;9            for (int j = 0; j < m; j++) {10                boolean identical = true;11                boolean complement = true;12                for (int k = 0; k < n; k++) {13                    if (matrix[i][k] != matrix[j][k]) {14                        identical = false;15                    }16                    if (matrix[i][k] == matrix[j][k]) {17                        complement = false;18                    }19                }20                if (identical || complement) {21                    count++;22                }23            }24            if (count > max) {25                max = count;26            }27        }28        return max;29    }30}

Complexity

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.

Trade-offs

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).

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.

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.

Walkthrough

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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    public int maxEqualRowsAfterFlips(int[][] matrix) {6        Map<String, Integer> patternCount = new HashMap<>();7        int n = matrix[0].length;8 9        for (int[] row : matrix) {10            StringBuilder sb = new StringBuilder();11            int firstElement = row[0];12            for (int j = 0; j < n; j++) {13                // Normalize the row by XORing with the first element.14                // This ensures the canonical pattern always starts with '0'.15                sb.append(row[j] ^ firstElement);16            }17            String key = sb.toString();18            patternCount.put(key, patternCount.getOrDefault(key, 0) + 1);19        }20 21        int max = 0;22        for (int count : patternCount.values()) {23            if (count > max) {24                max = count;25            }26        }27 28        return max;29    }30}

Complexity

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`.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class 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 ())

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem