Scale Engineer

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
ArrayHash TableMatrix

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.

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

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

Solutions

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

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 →

Next problem