# Cells with Odd Values in a Matrix LeetCode Solution

Difficulty Level Easy

## Problem Statement

Cells with Odd Values in a Matrix LeetCode Solution –  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] = [r`i`, c`i`]` represents a 0-indexed location to perform some increment operations on the matrix.

For each location `indices[i]`, we need to do both of the following:

1. Increment all the cells on row `r`i.
2. Increment all the cells on the column `c`i.

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

```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

`.` ## Explanation

A brute-force approach that also gets accepted due to low constraints in the question is to traverse for every row-col pair in indices and increment the matrix.
Finally, calculate the odd valued numbers.
This approach will take  : O (i * (m+n)) time with O(m*n) space

We are going to discuss an optimized solution in the article, so let’s move to that.

### Intuition

Each time a row or a column is encountered in the indices array it gets incremented, so if that row/column is a there an odd number of times in the indices array then the result of that row/column will be odd.

Two things to note here are:

1. if x rows are odd and y columns are odd the x*y elements will become even as they will be common in both row and col. (So we need to subtract them : x*y)
2. If x rows are odd then x*n elements will be counted and if y columns are odd then y*m elements will be counted but due to this elements with row=column will be counted twice (so we need to subtract them: -x*y)

So now then final equation will be :

Ans  : odd_row * n + odd_col * m – 2 * odd_row * odd_col

### The above equation can further be simplified to: odd_row * even_col + odd_col * even_row

#### HOW ??

(Replace n with : odd_col + even_col and m with : odd_row+even_row )

Now the only task left is to get odd rows and odd columns. For this, we will use the Bitwise XOR operator. Which you can see in the code.

## Code

### Java Program for Cells with Odd Values in a Matrix LeetCode Solution

```class Solution {
public int oddCells(int n, int m, int[][] indices) {
boolean[] oddRows = new boolean[n], oddCols = new boolean[m];
int cntRow = 0, cntCol = 0;
for (int[] idx : indices) {
oddRows[idx] ^= true;
oddCols[idx] ^= true;
}
for (boolean r : oddRows)
cntRow += r ? 1 : 0;
for (boolean c : oddCols)
cntCol += c ? 1 : 0;
// return m * cntRow + n * cntCol - 2 * cntRow * cntCol;
return (m - cntCol) * cntRow + (n - cntRow) * cntCol;
}
}```

### C++ Program for Cells with Odd Values in a Matrix LeetCode Solution

```class Solution {
public:
int oddCells(int n, int m, vector<vector<int>>& indices) {
vector<bool> N(n, false);
vector<bool> M(m, false);

for(int i=0; i<indices.size(); i++) {
N[indices[i]] = N[indices[i]]^true;
M[indices[i]] = M[indices[i]]^true;
}

int r = 0;
int c = 0;

for(int i=0; i<n; i++) {
if(N[i])
r++;
}

for(int j=0; j<m; j++) {
if(M[j])
c++;
}

return  r*m + c*n - 2*r*c;
}
};```

### Python Program for Cells with Odd Values in a Matrix LeetCode Solution

```class Solution:
def oddCells(self, n: int, m: int, indices: List[List[int]]) -> int:
odd_rows, odd_cols = [False] * n, [False] * m
for r, c in indices:
odd_rows[r] ^= True
odd_cols[c] ^= True
# return m * sum(odd_rows) + n * sum(odd_cols) - 2 * sum(odd_rows) * sum(odd_cols)
return (m - sum(odd_cols)) * sum(odd_rows) + (n - sum(odd_rows))* sum(odd_cols)
```

## Complexity Analysis for Cells with Odd Values in a Matrix LeetCode Solution

### Time Complexity

Time: O(L + m + n)

### Space Complexity

space: O(m + n), where L = indices.length.

Translate »