Problem Explanation

The problem gives us the dimensions n and m of a matrix initialized with zeros. It also provides an array indices where indices[i] = [ri, ci]. For each pair of [ri, ci], we are required to increment all cells in row ri and column ci by 1.

The goal is to return the number of cells with odd values in the matrix after incrementing all given indices.

Let's take an example:

Example 1: Input: n = 2, m = 3, indices = [[0,1],[1,1]] Output: 6

Here, the initial matrix is [[0,0,0],[0,0,0]]. After applying the first increment (for [0,1]), matrix becomes [[1,2,1],[0,1,0]]. Applying the next increment (for [1,1]), it becomes [[1,3,1],[1,3,1]]. We are then asked to count the number of odd numbers, which are 6 in this case.

Approach

The solution uses a xor based approach, where each element in the row is xored with true, and then, each element in the column is xored with true. The xor operation essentially helps to track the even and odd increments, as every true (1) will flip the value of the cell and every false (0) will keep it the same. So, each cell that gets true an odd number of times will end up holding an odd number. Hence, the final matrix's cells with odd value are actually the cells that get true an odd number of times.

Python Solution

1
2python
3class Solution:
4    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
5        cols = [0] * n
6        rows = [0] * m
7        for r, c in indices:
8            rows[r] ^= 1
9            cols[c] ^= 1
10
11        row_odd = sum(rows)
12        col_odd = sum(cols)
13        row_even = m - row_odd
14        col_even = n - col_odd
15
16        return row_odd * col_even + row_even * col_odd

Java Solution

1
2java
3class Solution {
4    public int oddCells(int m, int n, int[][] indices) {
5        boolean[] oddRows = new boolean[m], oddCols = new boolean[n];
6        for (int[] idx : indices) {
7            oddRows[idx[0]] ^= true;
8            oddCols[idx[1]] ^= true;
9        }
10        int cnt = 0;
11        for (boolean r : oddRows)
12            for (boolean c : oddCols)
13                cnt += r ^ c ? 1 : 0;
14        return cnt;
15    }
16}

JavaScript Solution

1
2javascript
3var oddCells = function(m, n, indices) {
4    let rows = new Array(m).fill(false),
5        cols = new Array(n).fill(false);
6
7    indices.forEach(([r, c]) => {
8        rows[r] = !rows[r];
9        cols[c] = !cols[c];
10    });
11
12    let oddRows = rows.reduce((a, v) => a + v, 0),
13        oddCols = cols.reduce((a, v) => a + v, 0);
14
15    return oddRows * (n - oddCols) + (m - oddRows) * oddCols;
16};

C++ Solution

1
2cpp
3class Solution {
4public:
5    int oddCells(int m, int n, vector<vector<int>>& indices) {
6        vector<int> oddRows(m, 0), oddCols(n, 0);
7        for (auto& index : indices) {
8            oddRows[index[0]] ^= 1;
9            oddCols[index[1]] ^= 1;
10        }
11        int cnt = 0;
12        for (int i = 0; i < m; ++i)
13            for (int j = 0; j < n; ++j)
14                cnt += oddRows[i] ^ oddCols[j];
15        return cnt;
16    }
17};

C# Solution

1
2csharp
3public class Solution {
4    public int OddCells(int m, int n, int[][] indices) {
5        bool[] oddRows = new bool[m], oddCols = new bool[n];
6        foreach (int[] index in indices) {
7            oddRows[index[0]] ^= true;
8            oddCols[index[1]] ^= true;
9        }
10        int count = 0;
11        for (int i = 0; i < m; i++)
12            for (int j = 0; j < n; j++)
13                if ((oddRows[i] ^ oddCols[j]) == true) 
14                    count++;
15        return count;
16    }
17}

As we see, each solution follows the same method of tracking and counting odd numbers in the final matrix by flipping (xor) the values in each row and column according to the indices.# Swift Solution

We can also implement the solution in Swift by applying the logic we used above.

1
2swift
3class Solution {
4    func oddCells(_ m: Int, _ n: Int, _ indices: [[Int]]) -> Int {
5        var oddRows = Array(repeating: false, count: m)
6        var oddCols = Array(repeating: false, count: n)
7        
8        for index in indices {
9            oddRows[index[0]] = !oddRows[index[0]]
10            oddCols[index[1]] = !oddCols[index[1]]
11        }
12        
13        var oddCount = 0
14        for i in 0..<m {
15            for j in 0..<n {
16                if oddRows[i] != oddCols[j] {
17                    oddCount += 1
18                }
19            }
20        }
21        return oddCount
22    }
23}

In the Swift implementation, we first initialize two arrays oddRows and oddCols with length m and n respectively and set all the values to false. We update the values of oddRows and oddCols to its opposite value at the position specified by the indices. Then, we scan the entire matrix by checking when the values at the same positions in oddRows and oddCols are not equal, which means the corresponding cell in the matrix would contain an odd number, so we increment oddCount.

Time and Space Complexity

The time complexity of the solution is O(m*n) as it involves scanning through all cells of the matrix.

The space complexity is O(m+n), needed to keep two additional arrays for rows and columns.

It is important to note that these time and space complexity assessments are valid for all versions of the solution, regardless of programming language used.