Given a matrix consisting of 0s and 1s, we may choose any number of columns in the matrix and flip every cell in that column. Flipping a cell changes the value of that cell from 0 to 1 or from 1 to 0.
Return the maximum number of rows that have all values equal after some number of flips.
Example 1:
Input: [[0,1],[1,1]]
Output: 1
Explanation: After flipping no values, 1 row has all values equal.
Example 2:
Input: [[0,1],[1,0]]
Output: 2
Explanation: After flipping values in the first column, both rows have equal values.
Example 3:
Input: [[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.
Note:
1 <= matrix.length <= 300
1 <= matrix[i].length <= 300
All matrix[i].length's are equal
matrix[i][j] is 0 or 1
class Solution {
public int maxEqualRowsAfterFlips(int[][] matrix) {
// We can make a single row into full 1s OR 0s
if (matrix.length == 1)
return 1;
Map<String, Integer> map = new HashMap<>();
int max = 0;
// Observation -> 2 rows which are opposite of each other will become full on
// same column flips
for (int i = 0; i < matrix.length; i++) {
StringBuilder str1 = new StringBuilder();
StringBuilder str2 = new StringBuilder();
for (int j = 0; j < matrix[i].length; j++) {
str1.append(1 - matrix[i][j]);
str2.append(matrix[i][j]);
}
String key1 = str1.toString(), key2 = str2.toString();
map.put(key1, map.getOrDefault(key1, 0) + 1);
max = Math.max(max, map.get(key1));
map.put(key2, map.getOrDefault(key2, 0) + 1);
max = Math.max(max, map.get(key2));
}
return max;
}
}