# 1252. 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:

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:

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

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

``````class Solution {
public:
int oddCells(int m, int n, vector<vector<int>>& indices) {
int res = 0;
vector<int> rowCnt(m), colCnt(n);
for (auto idx : indices) {
++rowCnt[idx[0]];
++colCnt[idx[1]];
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
res += (rowCnt[i] + colCnt[j]) % 2;
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1252

https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/

https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/discuss/425100/JavaPython-3-2-methods%3A-time-O(m-*-n-%2B-L)-and-O(L)-codes-w-comment-and-analysis.

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation