Cells with Odd Values in a Matrix: Row and Column Parity
You are given two integers n and m representing a matrix of size n x m initialized to all zeros, plus an array indices where each indices[i] = [ri, ci] means you increment every value in row ri and every value in column ci by 1. After applying all operations from indices, return the number of cells in the matrix with odd values.
This is LeetCode 1252: Cells with Odd Values in a Matrix, and it is a great example of how a simple simulation problem hides a clean mathematical optimization. The brute force works, but the parity counting approach runs faster and uses less memory.
Why this problem matters
The brute force approach is tempting: build the matrix, apply every increment, then count the odd cells. It works fine for small inputs. But the parity counting insight here teaches you a general lesson. When you only care about whether values are odd or even, you do not need to track the exact values at all. You just need to track whether each row and column received an odd or even number of increments.
This kind of reasoning, reducing a problem from "compute exact values" to "compute only the property you need," shows up in many optimization problems. Learning to spot it here makes you faster at recognizing it in harder problems.
The key insight
A cell at position (r, c) gets incremented once for every index that targets row r and once for every index that targets column c. So the total number of increments to cell (r, c) equals row_count[r] + col_count[c], where row_count[r] is how many times row r appears in the indices and col_count[c] is how many times column c appears.
A cell ends up with an odd value if and only if row_count[r] + col_count[c] is odd. The sum of two integers is odd when exactly one of them is odd. So you need either row_count[r] to be odd and col_count[c] to be even, or row_count[r] to be even and col_count[c] to be odd.
Count the number of rows with an odd increment count (call it odd_rows) and the number of columns with an odd increment count (call it odd_cols). Then even_rows = n - odd_rows and even_cols = m - odd_cols. The answer is:
odd_rows * even_cols + even_rows * odd_cols
The solution
def oddCells(n: int, m: int, indices: list[list[int]]) -> int:
row_count = [0] * n
col_count = [0] * m
for r, c in indices:
row_count[r] += 1
col_count[c] += 1
odd_rows = sum(1 for x in row_count if x % 2 == 1)
odd_cols = sum(1 for x in col_count if x % 2 == 1)
return odd_rows * (m - odd_cols) + (n - odd_rows) * odd_cols
The first loop tallies how many times each row and each column gets incremented. It iterates through the indices array once.
The next two lines count how many rows have an odd increment count and how many columns have an odd increment count. These are single passes over the row and column arrays.
The final line combines them. Cells where the row is odd and the column is even contribute odd_rows * even_cols. Cells where the row is even and the column is odd contribute even_rows * odd_cols. Together, these give the total number of odd-valued cells.
You never need to build the actual matrix. Since you only care about parity, tracking increment counts per row and per column is enough. This drops your space from O(n * m) to O(n + m).
Visual walkthrough
Let's trace through the example with n = 2, m = 3, and indices = [[0,1],[1,1]]. Watch how we track row and column counts instead of building the full matrix.
Step 1: Initialize a 2x3 matrix of zeros and count arrays.
row_count = [0, 0], col_count = [0, 0, 0]. All cells are 0.
Step 2: Process indices[0] = [0, 1]. Increment row_count[0] and col_count[1].
row_count = [1, 0], col_count = [0, 1, 0]. Row 0 and col 1 are highlighted.
Step 3: Process indices[1] = [1, 1]. Increment row_count[1] and col_count[1].
row_count = [1, 1], col_count = [0, 2, 0]. Row 1 and col 1 are highlighted.
Step 4: Count parities. odd_rows = 2, even_rows = 0, odd_cols = 0, even_cols = 3.
Both row counts are odd (1 and 1). All column counts are even (0, 2, 0).
Step 5: Apply the formula. Answer = odd_rows * even_cols + even_rows * odd_cols.
odd_rows(2) * even_cols(3) + even_rows(0) * odd_cols(0) = 6
2 * 3 + 0 * 0 = 6. Every cell has an odd value.
Both rows got incremented once (odd), and column 1 got incremented twice (even) while columns 0 and 2 got incremented zero times (even). So odd_rows = 2, odd_cols = 0, and the answer is 2 * 3 + 0 * 0 = 6.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Simulation | O(L * (n + m)) | O(n * m) |
| Row/column parity | O(L + n + m) | O(n + m) |
Time: The simulation approach processes each of the L index pairs by incrementing an entire row (m cells) and an entire column (n cells), giving O(L * (n + m)). The parity approach processes each index pair in O(1) by just incrementing two counters, then does a single pass over the row and column arrays, giving O(L + n + m).
Space: The simulation approach builds the full n * m matrix. The parity approach only stores the row_count and col_count arrays, which together use O(n + m) space.
The building blocks
1. Parity counting
When you only need to know whether a value is odd or even, you can replace exact value tracking with a simple count modulo 2:
odd_rows = sum(1 for x in row_count if x % 2 == 1)
This pattern appears any time a problem asks about odd/even properties. You do not need the actual numbers. You just need to know how many of them are odd. This same idea shows up in XOR problems, toggling problems, and light-switch puzzles.
2. Row/column decomposition
When operations target entire rows or columns, you can decompose the effect on each cell into its row contribution and column contribution:
row_count = [0] * n
col_count = [0] * m
for r, c in indices:
row_count[r] += 1
col_count[c] += 1
Instead of applying updates to every cell in a row or column, you record the update at the row or column level. The value at cell (r, c) is then row_count[r] + col_count[c]. This decomposition applies to any problem where operations affect entire rows, columns, or both. You will see it in Set Matrix Zeroes, Range Addition, and similar problems.
Edge cases
- Empty indices array: no increments happen. Every cell stays 0 (even). Return 0.
- All indices target the same row and column: row_count has one entry incremented L times, col_count has one entry incremented L times. The parity depends on whether L is odd or even.
- Single row or single column matrix:
n = 1orm = 1. The formula still works because odd_rows and odd_cols are just 0 or 1. - Large n and m with few indices: the matrix could be huge, but the parity approach only allocates O(n + m) space, not O(n * m).
- Duplicate indices: the same [r, c] pair can appear multiple times. Each occurrence increments row_count[r] and col_count[c] again, which is handled naturally.
From understanding to recall
You have seen that the trick is to avoid building the matrix entirely and instead count row and column increment parities. The formula odd_rows * even_cols + even_rows * odd_cols follows directly from the observation that a sum of two numbers is odd when exactly one of them is odd.
The hard part in an interview is not understanding this. It is remembering to look for it. Under pressure, the brute force simulation feels safe and obvious. The parity decomposition requires you to pause and ask: "Do I really need the exact values, or just their parity?" That question does not come naturally unless you have practiced it.
Spaced repetition builds that instinct. You practice recognizing when row/column decomposition applies and when parity counting replaces exact computation. After a few rounds, the pattern triggers automatically. You see "increment entire rows and columns" in a problem statement, and the decomposition is immediate.
Related posts
- Set Matrix Zeroes - Another problem where row and column operations interact at each cell
- Game of Life - Matrix transformation where you track state changes per cell
- Flipping an Image - Simple matrix manipulation with a clean optimization
CodeBricks breaks Cells with Odd Values in a Matrix into its parity counting and row/column decomposition building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a matrix problem shows up in your interview, you do not think about it. You just write it.