There is an m x n matrix that is initialized to all 0's. There is also a 2D array indices where each indices[i] = [ri, ci] represents a 0-indexed location to perform some increment operations on the matrix.

For each location indices[i], do both of the following:


	Increment all the cells on row ri.
	Increment all the cells on column ci.


Given m, n, and indices, return the number of odd-valued cells in the matrix after applying the increment to all locations in indices.

&nbsp;
Example 1:

Input: m = 2, n = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Initial matrix = [[0,0,0],[0,0,0]].
After applying first increment it becomes [[1,2,1],[0,1,0]].
The final matrix is [[1,3,1],[1,3,1]], which contains 6 odd numbers.


Example 2:

Input: m = 2, n = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]]. There are no odd numbers in the final matrix.


&nbsp;
Constraints:


	1 &lt;= m, n &lt;= 50
	1 &lt;= indices.length &lt;= 100
	0 &lt;= ri &lt; m
	0 &lt;= ci &lt; n


&nbsp;
Follow up: Could you solve this in O(n + m + indices.length) time with only O(n + m) extra space?

class Solution:
    def oddCells(self, row: int, col: int, indices: List[List[int]]) -> int:
        rows, cols = [False] * row, [False] * col

        for index in indices:
            rows[index[0]] = not rows[index[0]]
            cols[index[1]] = not cols[index[1]]

        count = 0
        for i in rows:
            for j in cols:
                count += i ^ j

        return count
// --------------------- Solution 1 ---------------------
class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[][] matrix = new int[m][n];
        
        for(int i = 0; i < indices.length; i++) {
            int row = indices[i][0];
            int col = indices[i][1];
            
            for(int j = 0; j < n; j++) {
                matrix[row][j]++;
            }
            for(int j = 0; j < m; j++) {
                matrix[j][col]++;
            }
        }
        
        int counter = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(matrix[i][j] % 2 != 0) {
                    counter++;
                }
            }
        }
        
        return counter;
    }
}

// --------------------- Solution 2 ---------------------
class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[] row = new int[m];
        int[] col = new int[n];
        
        for(int i = 0; i < indices.length; i++) {
            row[indices[i][0]]++;
            col[indices[i][1]]++;
        }
        
        int counter = 0;
        for(int i : row) {
            for(int j : col) {
                counter += (i + j) % 2 == 0 ? 0 : 1;
            }
        }
        
        return counter;
    }
}
static int x = []() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0; }();

class Solution { // tc: O(n+m) & sc: O(n+m)
public:
    int oddCells(int n, int m, vector<vector<int>>& indices) {
        vector<bool> rows(n,false),cols(m,false);
        for(auto index: indices){
            rows[index[0]] = rows[index[0]] ^ true;
            cols[index[1]] = cols[index[1]] ^ true;
        }
        
        int r(0),c(0);
        for(int i(0);i<n;i++){
            if(rows[i]) r++;
        }
        
        for(int i(0);i<m;i++){
            if(cols[i]) c++;
        }
        return r*(m-c) + c*(n-r); // (or) return (r*m + c*n - 2*r*c);
    }
};
var oddCells = function(m, n, indices) {
    const matrix = Array.from(Array(m), () => Array(n).fill(0));

    let res = 0;
    for (const [r, c] of indices) {
        for (let i = 0; i < n; i++) {
            // toggle 0/1 for even/odd
            // another method: matrix[r][i] = 1 - matrix[r][i]
            // or: matrix[r][i] = +!matrix[r][i]
            matrix[r][i] ^= 1;
            if (matrix[r][i]) res++; else res--;
        }

        for (let i = 0; i < m; i++) {
            matrix[i][c] ^= 1;
            if (matrix[i][c]) res++; else res--;
        }
    }

    return res;
};
Cells with Odd Values in a Matrix