Cells with Odd Values in a Matrix
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:
- Increment all the cells on row
ri. - 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.
Follow up: Could you solve this in O(n + m + indices.length) time with only O(n + m) extra space?
Example 1
Input
m = 2, n = 3, indices = [[0,1],[1,1]]Output
6Initial matrix is [[0,0,0],[0,0,0]]; after both increments the final matrix is [[1,3,1],[1,3,1]], which contains 6 odd numbers.
Example 2
Input
m = 2, n = 2, indices = [[1,1],[0,0]]Output
0The final matrix is [[2,2],[2,2]], so there are no odd numbers.
Constraints
- 1 <= m, n <= 50
- 1 <= indices.length <= 100
- 0 <= ri < m
- 0 <= ci < n