LeetCode 1252: Cells With Odd Values in a Matrix (Row/Column Parity Counting)
LeetCode 1252MatrixParityCountingToday we solve LeetCode 1252 - Cells With Odd Values in a Matrix.
Source: https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/
English
Problem Summary
You are given an m x n matrix initialized with zeros and a list indices. For each pair [ri, ci], increment every cell in row ri and every cell in column ci by 1. Return the number of cells with odd values.
Key Insight
Only odd/even parity matters. A row increment flips parity for all cells in that row; a column increment flips parity for all cells in that column. So we only track whether each row/column is flipped an odd number of times.
Brute Force and Limitations
Direct simulation updates all m + n cells per operation, then scans the full matrix: O(k(m+n) + mn). Correct but unnecessary when constraints grow.
Optimal Algorithm Steps
1) Maintain boolean parity arrays rowOdd[m] and colOdd[n].
2) For each [r,c], toggle rowOdd[r] and colOdd[c].
3) Count rOdd = #true(rowOdd), cOdd = #true(colOdd).
4) Odd cells count is rOdd * (n - cOdd) + (m - rOdd) * cOdd.
Complexity Analysis
Time: O(k + m + n).
Space: O(m + n).
Common Pitfalls
- Using integer counters and forgetting to reduce to parity.
- Double counting overlap between odd rows and odd columns.
- Returning rOdd * cOdd by mistake (that counts even cells after two flips).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int oddCells(int m, int n, int[][] indices) {
boolean[] rowOdd = new boolean[m];
boolean[] colOdd = new boolean[n];
for (int[] idx : indices) {
rowOdd[idx[0]] = !rowOdd[idx[0]];
colOdd[idx[1]] = !colOdd[idx[1]];
}
int rOdd = 0, cOdd = 0;
for (boolean b : rowOdd) if (b) rOdd++;
for (boolean b : colOdd) if (b) cOdd++;
return rOdd * (n - cOdd) + (m - rOdd) * cOdd;
}
}func oddCells(m int, n int, indices [][]int) int {
rowOdd := make([]bool, m)
colOdd := make([]bool, n)
for _, idx := range indices {
r, c := idx[0], idx[1]
rowOdd[r] = !rowOdd[r]
colOdd[c] = !colOdd[c]
}
rOdd, cOdd := 0, 0
for _, b := range rowOdd {
if b {
rOdd++
}
}
for _, b := range colOdd {
if b {
cOdd++
}
}
return rOdd*(n-cOdd) + (m-rOdd)*cOdd
}class Solution {
public:
int oddCells(int m, int n, vector<vector<int>>& indices) {
vector<bool> rowOdd(m, false), colOdd(n, false);
for (auto& idx : indices) {
rowOdd[idx[0]] = !rowOdd[idx[0]];
colOdd[idx[1]] = !colOdd[idx[1]];
}
int rOdd = 0, cOdd = 0;
for (bool b : rowOdd) if (b) rOdd++;
for (bool b : colOdd) if (b) cOdd++;
return rOdd * (n - cOdd) + (m - rOdd) * cOdd;
}
};class Solution:
def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
row_odd = [False] * m
col_odd = [False] * n
for r, c in indices:
row_odd[r] = not row_odd[r]
col_odd[c] = not col_odd[c]
r_odd = sum(row_odd)
c_odd = sum(col_odd)
return r_odd * (n - c_odd) + (m - r_odd) * c_oddvar oddCells = function(m, n, indices) {
const rowOdd = Array(m).fill(false);
const colOdd = Array(n).fill(false);
for (const [r, c] of indices) {
rowOdd[r] = !rowOdd[r];
colOdd[c] = !colOdd[c];
}
let rOdd = 0, cOdd = 0;
for (const v of rowOdd) if (v) rOdd++;
for (const v of colOdd) if (v) cOdd++;
return rOdd * (n - cOdd) + (m - rOdd) * cOdd;
};中文
题目概述
给定一个初始全 0 的 m x n 矩阵，以及操作数组 indices。每次操作 [ri, ci] 会让第 ri 行和第 ci 列全部加 1。返回最终奇数值单元格的数量。
核心思路
题目只关心奇偶性，不关心具体数值。某行被操作一次就会翻转该行所有格子的奇偶；某列同理。所以只要记录每行/每列是否被翻转了奇数次。
暴力解法与不足
直接维护矩阵，每次把整行整列加一，最后统计奇数。时间复杂度为 O(k(m+n)+mn)，可做但不够精炼。
最优算法步骤
1）使用 rowOdd[m]、colOdd[n] 记录奇偶翻转状态。
2）遍历 indices，对对应行列执行布尔取反。
3）统计奇数行数量 rOdd 和奇数列数量 cOdd。
4）答案为 rOdd * (n - cOdd) + (m - rOdd) * cOdd。
复杂度分析
时间复杂度：O(k + m + n)。
空间复杂度：O(m + n)。
常见陷阱
- 用计数数组后忘记只取奇偶（模 2）。
- 没处理奇数行和奇数列交叉位置导致统计错误。
- 误把 rOdd * cOdd 当答案（该部分实际是偶数格）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int oddCells(int m, int n, int[][] indices) {
boolean[] rowOdd = new boolean[m];
boolean[] colOdd = new boolean[n];
for (int[] idx : indices) {
rowOdd[idx[0]] = !rowOdd[idx[0]];
colOdd[idx[1]] = !colOdd[idx[1]];
}
int rOdd = 0, cOdd = 0;
for (boolean b : rowOdd) if (b) rOdd++;
for (boolean b : colOdd) if (b) cOdd++;
return rOdd * (n - cOdd) + (m - rOdd) * cOdd;
}
}func oddCells(m int, n int, indices [][]int) int {
rowOdd := make([]bool, m)
colOdd := make([]bool, n)
for _, idx := range indices {
r, c := idx[0], idx[1]
rowOdd[r] = !rowOdd[r]
colOdd[c] = !colOdd[c]
}
rOdd, cOdd := 0, 0
for _, b := range rowOdd {
if b {
rOdd++
}
}
for _, b := range colOdd {
if b {
cOdd++
}
}
return rOdd*(n-cOdd) + (m-rOdd)*cOdd
}class Solution {
public:
int oddCells(int m, int n, vector<vector<int>>& indices) {
vector<bool> rowOdd(m, false), colOdd(n, false);
for (auto& idx : indices) {
rowOdd[idx[0]] = !rowOdd[idx[0]];
colOdd[idx[1]] = !colOdd[idx[1]];
}
int rOdd = 0, cOdd = 0;
for (bool b : rowOdd) if (b) rOdd++;
for (bool b : colOdd) if (b) cOdd++;
return rOdd * (n - cOdd) + (m - rOdd) * cOdd;
}
};class Solution:
def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
row_odd = [False] * m
col_odd = [False] * n
for r, c in indices:
row_odd[r] = not row_odd[r]
col_odd[c] = not col_odd[c]
r_odd = sum(row_odd)
c_odd = sum(col_odd)
return r_odd * (n - c_odd) + (m - r_odd) * c_oddvar oddCells = function(m, n, indices) {
const rowOdd = Array(m).fill(false);
const colOdd = Array(n).fill(false);
for (const [r, c] of indices) {
rowOdd[r] = !rowOdd[r];
colOdd[c] = !colOdd[c];
}
let rOdd = 0, cOdd = 0;
for (const v of rowOdd) if (v) rOdd++;
for (const v of colOdd) if (v) cOdd++;
return rOdd * (n - cOdd) + (m - rOdd) * cOdd;
};
Comments