Cells with Odd Values in a Matrix

Let’s break down the problem and write a simple algorithm to solve it.

We need to initialize an m by n matrix with zeros. Then for each [ri, ci] in indices, we need to increment all cells in row ri and column ci. Finally, we need to count the number of odd-valued cells in the matrix.

Here’s a step-by-step approach:

1. Initialize a matrix mat of size m by n with zeros.
2. Iterate through indices, and for each [ri, ci] do the following: a. Increment all the cells in row ri. b. Increment all the cells in column ci.
3. Iterate through the matrix and count the number of odd-valued cells.

Python solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        # Initialize matrix with zeros
        mat = [[0] * n for _ in range(m)]

        # Apply increments to rows and columns
        for ri, ci in indices:
            # Increment the entire row ri
            for j in range(n):
                mat[ri][j] += 1

            # Increment the entire column ci
            for i in range(m):
                mat[i][ci] += 1

        # Count odd numbers in the matrix
        count = 0
        for i in range(m):
            for j in range(n):
                if mat[i][j] % 2 != 0:
                    count += 1

        return count

The code iterates through the matrix and the indices array, so the time complexity is (O(m \cdot n + k)), where (k) is the length of the indices array. The space complexity is (O(m \cdot n)) for the matrix.