# 1252. Cells with Odd Values in a Matrix¶

## Approach 1: Traverse all cells¶

• Time: $O(mn + |\texttt{indices}|)$
• Space: $O(m + n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int oddCells(int m, int n, vector>& indices) { int ans = 0; // rows[i] and cols[i] := // true (flipped even times) / false (flipped odd times) vector rows(m); vector cols(n); for (const vector& index : indices) { rows[index[0]] = rows[index[0]] ^ true; cols[index[1]] = cols[index[1]] ^ true; } for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) ans += rows[i] ^ cols[j]; return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int oddCells(int m, int n, int[][] indices) { int ans = 0; // rows[i] and cols[i] := // true (flipped even times) / false (flipped odd times) boolean[] rows = new boolean[n]; boolean[] cols = new boolean[n]; for (int[] index : indices) { rows[index[0]] = rows[index[0]] ^ true; cols[index[1]] = cols[index[1]] ^ true; } for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (rows[i] ^ cols[j]) ++ans; return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution: def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int: # rows[i] and cols[i] := # true (flipped even times) / false (flipped odd times) rows = [False] * m cols = [False] * n for r, c in indices: rows[r] ^= True cols[c] ^= True return sum(rows[i] ^ cols[j] for i in range(m) for j in range(n)) 

## Approach 2: Math¶

• Time: $O(m + n + |\texttt{indices}|)$
• Space: $O(m + n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public: int oddCells(int m, int n, vector>& indices) { // rows[i] and cols[i] := // 1. true (flipped even times) // 2. false (flipped odd times) vector rows(m); vector cols(n); for (const vector& index : indices) { rows[index[0]] = rows[index[0]] ^ true; cols[index[1]] = cols[index[1]] ^ true; } const int oddRowsCount = ranges::count(rows, true); const int oddColsCount = ranges::count(cols, true); const int evenRowsCount = m - oddRowsCount; const int evenColsCount = n - oddColsCount; return oddRowsCount * evenColsCount + oddColsCount * evenRowsCount; } }; 
  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 27 28 29 class Solution { public int oddCells(int m, int n, int[][] indices) { // rows[i] and cols[i] := // 1. true (flipped even times) // 2. false (flipped odd times) boolean[] rows = new boolean[n]; boolean[] cols = new boolean[n]; for (int[] index : indices) { rows[index[0]] = rows[index[0]] ^ true; cols[index[1]] = cols[index[1]] ^ true; } int oddRowsCount = 0; int oddColsCount = 0; for (boolean row : rows) if (row) ++oddRowsCount; for (boolean col : cols) if (col) ++oddColsCount; final int evenRowsCount = m - oddRowsCount; final int evenColsCount = n - oddColsCount; return oddRowsCount * evenColsCount + oddColsCount * evenRowsCount; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int: # rows[i] and cols[i] := # 1. True (flipped even times) # 2. False (flipped odd times) rows = [False] * m cols = [False] * n for r, c in indices: rows[r] ^= True cols[c] ^= True oddRowsCount = rows.count(True) oddColsCount = cols.count(True) evenRowsCount = m - oddRowsCount evenColsCount = n - oddColsCount return oddRowsCount * evenColsCount + oddColsCount * evenRowsCount 

## Approach 3: Math (Set)¶

• Time: $O(|\texttt{indices}|)$
• Space: $O(|\texttt{indices}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public: int oddCells(int m, int n, vector>& indices) { unordered_set oddRows; unordered_set oddCols; for (const vector& index : indices) { const int r = index[0]; const int c = index[1]; if (!oddRows.insert(r).second) oddRows.erase(r); if (!oddCols.insert(c).second) oddCols.erase(c); } return oddRows.size() * (n - oddCols.size()) + oddCols.size() * (m - oddRows.size()); } };