Skip to content

1072. Flip Columns For Maximum Number of Equal Rows 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
    const int m = matrix.size();
    const int n = matrix[0].size();
    int ans = 0;
    vector<int> flip(n);
    unordered_set<int> seen;

    for (int i = 0; i < m; ++i) {
      if (seen.contains(i))
        continue;
      int count = 0;
      for (int j = 0; j < n; ++j)
        flip[j] = 1 ^ matrix[i][j];
      for (int k = 0; k < m; ++k)
        if (matrix[k] == matrix[i] || matrix[k] == flip) {
          seen.insert(k);
          ++count;
        }
      ans = max(ans, count);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int maxEqualRowsAfterFlips(int[][] matrix) {
    final int m = matrix.length;
    final int n = matrix[0].length;
    int ans = 0;
    int[] flip = new int[n];
    Set<Integer> seen = new HashSet<>();

    for (int i = 0; i < m; ++i) {
      if (seen.contains(i))
        continue;
      int count = 0;
      for (int j = 0; j < n; ++j)
        flip[j] = 1 ^ matrix[i][j];
      for (int k = 0; k < m; ++k)
        if (Arrays.equals(matrix[k], matrix[i]) || Arrays.equals(matrix[k], flip)) {
          seen.add(k);
          ++count;
        }
      ans = Math.max(ans, count);
    }

    return ans;
  }
}

1
2
3
4
class Solution:
  def maxEqualRowsAfterFlips(self, matrix: list[list[int]]) -> int:
    patterns = [tuple(a ^ row[0] for a in row) for row in matrix]
    return max(Counter(patterns).values())