# Cells with Odd Values in a Matrix
**Difficulty:** EASY
[External](https://leetcode.com/problems/cells-with-odd-values-in-a-matrix)
Canonical: https://scaleengineer.com/dsa/problems/cells-with-odd-values-in-a-matrix
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
---
## Problem
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:

1. Increment **all** the cells on row `ri`.
2. 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`.

**Example 1:**

![](https://assets.glich.co/dsa/cells-with-odd-values-in-a-matrix/image0.png) 

**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:**

![](https://assets.glich.co/dsa/cells-with-odd-values-in-a-matrix/image1.png) 

**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.

**Constraints:**

* `1 <= m, n <= 50`
* `1 <= indices.length <= 100`
* `0 <= ri < m`
* `0 <= ci < n`

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

# Approaches
## Direct Simulation
This approach directly simulates the process described in the problem. It involves creating an `m x n` matrix, iterating through each index pair in `indices` to increment the corresponding rows and columns, and finally, traversing the entire matrix to count the cells with odd values.
**Time:** O(indices.length * (m + n) + m * n). For each of the `indices.length` operations, we traverse a row of `n` elements and a column of `m` elements. After all operations, we traverse the `m * n` matrix to count odd cells. · **Space:** O(m * n) to store the matrix.
**Pros:** Simple to understand and implement as it directly follows the problem statement.
**Cons:** Inefficient in both time and space, especially for large matrices.; The space complexity of O(m * n) can be prohibitive if m and n are large.
### Explanation
The most straightforward way to solve the problem is to follow the instructions literally. We create a 2D array that represents the matrix and initialize it with zeros. Then, for each entry in the `indices` array, we iterate through the specified row and column, incrementing each cell's value. After all increment operations are complete, we perform a final pass over the entire matrix to count how many cells contain an odd number.

```java
class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[][] matrix = new int[m][n];
        
        for (int[] index : indices) {
            int r = index[0];
            int c = index[1];
            
            // Increment row r
            for (int j = 0; j < n; j++) {
                matrix[r][j]++;
            }
            
            // Increment column c
            for (int i = 0; i < m; i++) {
                matrix[i][c]++;
            }
        }
        
        int oddCount = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] % 2 != 0) {
                    oddCount++;
                }
            }
        }
        
        return oddCount;
    }
}
```
### Algorithm
- Initialize an `m x n` integer matrix, `matrix`, with all elements set to 0.
- Iterate through each pair `[r, c]` in the `indices` array.
- For each `[r, c]`, perform two sub-steps:
    - Increment every element in row `r`: Iterate from `j = 0` to `n-1` and increment `matrix[r][j]`.
    - Increment every element in column `c`: Iterate from `i = 0` to `m-1` and increment `matrix[i][c]`.
- Initialize a counter `odd_count` to 0.
- Iterate through the entire `matrix` from `i = 0` to `m-1` and `j = 0` to `n-1`.
- For each cell `matrix[i][j]`, check if its value is odd (i.e., `matrix[i][j] % 2 != 0`).
- If the value is odd, increment `odd_count`.
- Return `odd_count`.

## Auxiliary Arrays with Brute-Force Count
This approach avoids building the full matrix. It observes that the final value of a cell `(r, c)` is the sum of increments for row `r` and column `c`. We can use two auxiliary arrays to store the total number of times each row and column is incremented. Then, we can calculate the final value for each cell and check its parity.
**Time:** O(indices.length + m * n). We iterate through `indices` once, and then we iterate through all `m * n` conceptual cells. · **Space:** O(m + n) for the two auxiliary arrays.
**Pros:** More space-efficient than the simulation approach.; Time complexity is improved by avoiding repeated traversals of rows and columns.
**Cons:** The final counting step still requires iterating through `m * n` cells, which can be slow if `m` and `n` are large.
### Explanation
Instead of simulating the matrix operations directly, we can optimize by realizing that the final value of any cell `matrix[i][j]` is simply the sum of the number of times its row `i` was incremented and the number of times its column `j` was incremented. This allows us to avoid constructing the `m x n` matrix. We can use two separate arrays, one to keep track of the increment counts for each row and another for each column. After populating these count arrays by iterating through `indices`, we can then iterate through all `m * n` conceptual cell positions, calculate the final value for each, and count how many are odd.

```java
class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[] rowCounts = new int[m];
        int[] colCounts = new int[n];
        
        for (int[] index : indices) {
            rowCounts[index[0]]++;
            colCounts[index[1]]++;
        }
        
        int oddCount = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((rowCounts[i] + colCounts[j]) % 2 != 0) {
                    oddCount++;
                }
            }
        }
        
        return oddCount;
    }
}
```
### Algorithm
- Create an integer array `row_counts` of size `m`, initialized to zeros.
- Create an integer array `col_counts` of size `n`, initialized to zeros.
- Iterate through each pair `[r, c]` in the `indices` array:
    - Increment `row_counts[r]`.
    - Increment `col_counts[c]`.
- Initialize a counter `odd_count` to 0.
- Iterate from `i = 0` to `m-1` and `j = 0` to `n-1` (conceptually iterating through the matrix cells).
- For each pair `(i, j)`, calculate the final cell value: `value = row_counts[i] + col_counts[j]`.
- If `value` is odd, increment `odd_count`.
- Return `odd_count`.

## Optimized Counting with Auxiliary Arrays
This is the most efficient approach. It builds upon the previous idea but optimizes the final counting step. A cell `(r, c)` has an odd value if `row_counts[r] + col_counts[c]` is odd. This happens if one count is odd and the other is even. Instead of checking every cell, we can count the number of rows with odd increments (`odd_rows`) and columns with odd increments (`odd_cols`). The total number of odd cells is then `odd_rows * even_cols + even_rows * odd_cols`.
**Time:** O(indices.length + m + n). We iterate through `indices` once (`O(indices.length)`), then through the row parities (`O(m)`), and then the column parities (`O(n)`). · **Space:** O(m + n) for the two boolean arrays.
**Pros:** Highly efficient in both time and space.; It avoids the O(m * n) complexity entirely, making it suitable for large matrices.; Satisfies the follow-up constraints of the problem.
**Cons:** The logic is slightly more abstract than the direct simulation, which might make it harder to come up with initially.
### Explanation
This approach further optimizes the previous one by eliminating the `O(m * n)` loop. We only need to know the parity (odd or even) of the increment counts, not their exact values. A cell `(i, j)` will have an odd value if `row_counts[i]` is odd and `col_counts[j]` is even, or vice versa. 

We can first determine the parity for all row and column increments. We use two boolean arrays, `oddRows` and `oddCols`, to track this. After iterating through `indices` and flipping the boolean flags, we count the total number of rows with odd increments (`oddRowCount`) and columns with odd increments (`oddColCount`). The number of rows and columns with even increments are then `m - oddRowCount` and `n - oddColCount` respectively. The final answer is the number of cells in odd-increment rows and even-increment columns, plus the number of cells in even-increment rows and odd-increment columns. This can be calculated with a simple formula, avoiding the nested loops entirely.

```java
class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        boolean[] oddRows = new boolean[m];
        boolean[] oddCols = new boolean[n];
        
        for (int[] index : indices) {
            oddRows[index[0]] = !oddRows[index[0]];
            oddCols[index[1]] = !oddCols[index[1]];
        }
        
        int oddRowCount = 0;
        for (int i = 0; i < m; i++) {
            if (oddRows[i]) {
                oddRowCount++;
            }
        }
        
        int oddColCount = 0;
        for (int j = 0; j < n; j++) {
            if (oddCols[j]) {
                oddColCount++;
            }
        }
        
        int evenRowCount = m - oddRowCount;
        int evenColCount = n - oddColCount;
        
        return oddRowCount * evenColCount + evenRowCount * oddColCount;
    }
}
```
### Algorithm
- Create a boolean array `row_is_odd` of size `m` and `col_is_odd` of size `n`, initialized to `false`. These will track the parity of increments for each row and column.
- Iterate through each pair `[r, c]` in the `indices` array:
    - Flip the boolean value: `row_is_odd[r] = !row_is_odd[r]`.
    - Flip the boolean value: `col_is_odd[c] = !col_is_odd[c]`.
- Count the number of rows with an odd number of increments. Initialize `odd_rows_count = 0`. Iterate through `row_is_odd`, and if `row_is_odd[i]` is `true`, increment `odd_rows_count`.
- Count the number of columns with an odd number of increments. Initialize `odd_cols_count = 0`. Iterate through `col_is_odd`, and if `col_is_odd[j]` is `true`, increment `odd_cols_count`.
- The number of rows with an even number of increments is `even_rows_count = m - odd_rows_count`.
- The number of columns with an even number of increments is `even_cols_count = n - odd_cols_count`.
- A cell `(i, j)` is odd if its row increment count is odd and column is even, OR its row is even and column is odd.
- Calculate the total number of odd cells: `result = (odd_rows_count * even_cols_count) + (even_rows_count * odd_cols_count)`.
- Return `result`.

# Solutions
### Java

```java
class Solution {
public
  int oddCells(int m, int n, int[][] indices) {
    int[][] g = new int[m][n];
    for (int[] e : indices) {
      int r = e[0], c = e[1];
      for (int i = 0; i < m; ++i) {
        g[i][c]++;
      }
      for (int j = 0; j < n; ++j) {
        g[r][j]++;
      }
    }
    int ans = 0;
    for (int[] row : g) {
      for (int v : row) {
        ans += v % 2;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int oddCells(int m, int n, vector<vector<int>> &indices) {
    vector<vector<int>> g(m, vector<int>(n));
    for (auto &e : indices) {
      int r = e[0], c = e[1];
      for (int i = 0; i < m; ++i)
        ++g[i][c];
      for (int j = 0; j < n; ++j)
        ++g[r][j];
    }
    int ans = 0;
    for (auto &row : g)
      for (int v : row)
        ans += v % 2;
    return ans;
  }
};

```

### Python

```python
class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int: g = [[0] * n for _ in range(m)] for r, c in indices: for i in range(m): g[i][c] += 1 for j in range(n): g[r][j] += 1 return sum(v % 2 for row in g for v in row)

```