_1252.java

packagecom.fishercoder.solutions.secondthousand;

publicclass_1252 {
publicstaticclassSolution1 {
/*
 * Time: O(m*n + k) where k is the length of indices
 * Space: O(m*n)
 */
publicintoddCells(intn, intm, int[][] indices) {
int[][] matrix = newint[n][m];
for (inti = 0; i < indices.length; i++) {
addOneToRow(matrix, indices[i][0]);
addOneToColumn(matrix, indices[i][1]);
 }
intoddNumberCount = 0;
for (inti = 0; i < matrix.length; i++) {
for (intj = 0; j < matrix[0].length; j++) {
if (matrix[i][j] % 2 != 0) {
oddNumberCount++;
 }
 }
 }
returnoddNumberCount;
 }

privatevoidaddOneToColumn(int[][] matrix, intcolumnIndex) {
for (inti = 0; i < matrix.length; i++) {
matrix[i][columnIndex] += 1;
 }
 }

privatevoidaddOneToRow(int[][] matrix, introwIndex) {
for (intj = 0; j < matrix[0].length; j++) {
matrix[rowIndex][j] += 1;
 }
 }
 }

publicstaticclassSolution2 {
/*
 * Time: O(m*n + k) where k is the length of indices
 * Space: O(m + n)
 */
publicintoddCells(intn, intm, int[][] indices) {
boolean[] row = newboolean[n];
boolean[] column = newboolean[m];
for (int[] index : indices) {
row[index[0]] ^= true;
column[index[1]] ^= true;
 }
intoddNumberCount = 0;
for (inti = 0; i < n; i++) {
for (intj = 0; j < m; j++) {
oddNumberCount += row[i] ^ column[j] ? 1 : 0;
 }
 }
returnoddNumberCount;
 }
 }
}