【LeetCode】1252. Number of odd value cells

subject

1252. The number of odd cells

To give you one m x n Matrix , At the very beginning , The value in each cell is 0.

There is another two-dimensional index array indices,indices[i] = [ri, ci] Point to a position in the matrix , among ri and ci Respectively represent the specified row and column （ from 0 Numbered starting ）.

Yes indices[i] Every position pointed , The following incremental operations should be performed at the same time ：

1. ri All cells on the row , Add 1 .
2. ci All cells on the column , Add 1 .

Here you are. m、n and indices . Please finish executing all indices After the specified incremental operation , Back in the matrix Odd cells Number of .

Example 1：

 Input ：m = 2, n = 3, indices = [[0,1],[1,1]]
 Output ：6
 explain ： The initial matrix is  [[0,0,0],[0,0,0]].
 After the first incremental operation  [[1,2,1],[0,1,0]].
 The final matrix is  [[1,3,1],[1,3,1]], There are  6  An odd number .

Example 2：

 Input ：m = 2, n = 2, indices = [[1,1],[0,0]]
 Output ：0
 explain ： The final matrix is  [[2,2],[2,2]], There are no odd numbers in it .

Tips ：

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

** Advanced ：** You can design a time complexity of O(n + m + indices.length) And only O(n + m) Extra space algorithm to solve this problem ？

Ideas

• Because each operation is for an entire row or column , So declare two variables to save the changes of the row and column
• matrix[i][j] The change of is equivalent to the third i Xing He j Sum of changes in columns

Code

class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        row,col = [0] * m, [0] * n
        for r,c in indices:
            row[r] += 1
            col[c] += 1
        ret = 0
        for i in range(m):
            for j in range(n):
                if (row[i] + col[j])%2==1: ret +=1
        return ret

Complexity

• Time complexity ：$O(m+n+indices.length)$
• Spatial complexity ：$O(m+n)$