LeetCode 1252 - Cells with Odd Values in a Matrix
The problem gives us an m x n matrix where every cell initially contains 0. We are also given a list called indices, whe
Difficulty: 🟢 Easy
Topics: Array, Math, Simulation
Solution
Problem Understanding
The problem gives us an m x n matrix where every cell initially contains 0. We are also given a list called indices, where each element is a pair [ri, ci].
For every pair [ri, ci], we must perform two operations:
- Increment every value in row
riby1 - Increment every value in column
ciby1
After processing all operations, we need to count how many cells in the matrix contain odd numbers.
The important detail is that each operation affects an entire row and an entire column simultaneously. A cell may therefore be incremented multiple times across different operations. Whether a cell ends up odd or even depends only on the parity, meaning whether the total number of increments applied to it is odd or even.
The input consists of:
m, the number of rowsn, the number of columnsindices, the list of row-column increment operations
The output is a single integer representing the number of cells with odd values after all operations are complete.
The constraints are small:
1 <= m, n <= 50indices.length <= 100
These limits mean even a direct matrix simulation would work comfortably within time limits. However, the follow up asks for a more optimized solution using only O(m + n) extra space and avoiding full matrix simulation when possible.
Several edge cases are important to consider:
- Multiple operations may target the same row or column repeatedly
- A row or column may be incremented an even number of times, making its contribution effectively cancel out in parity terms
- Small matrices like
1 x 1can expose parity mistakes - Operations may affect every row and every column
- We only care about odd versus even, not the actual numeric values
Approaches
Brute Force Approach
The most straightforward solution is to explicitly simulate the matrix.
We create an m x n matrix initialized with zeros. For every [ri, ci] in indices, we iterate across the entire row ri and increment each value. Then we iterate across the entire column ci and increment each value.
After all operations are processed, we traverse the entire matrix and count how many cells contain odd values.
This approach is easy to understand and directly follows the problem statement, which makes correctness intuitive. Every operation is performed exactly as described.
However, this method performs unnecessary work. We repeatedly modify matrix values even though we only care about whether the final result is odd or even. The actual numeric value does not matter beyond parity.
The time complexity becomes:
- Each operation updates
nrow cells andmcolumn cells - Total complexity:
O(indices.length * (m + n)) - Final traversal adds
O(m * n)
Although this is acceptable for the given constraints, we can do better conceptually.
Optimal Approach
The key observation is that we only care about parity.
A cell (r, c) is incremented:
- Once for every operation targeting row
r - Once for every operation targeting column
c
Therefore, the final value of a cell is:
rowIncrements[r] + colIncrements[c]
A sum is odd if one part is odd and the other is even.
Instead of simulating the entire matrix, we can simply track:
- Whether each row has been incremented an odd or even number of times
- Whether each column has been incremented an odd or even number of times
Then for every cell:
- Odd row + even column = odd
- Even row + odd column = odd
We can count the result directly without storing matrix values.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(indices.length × (m + n) + m × n) | O(m × n) | Simulates the entire matrix explicitly |
| Optimal | O(indices.length + m × n) | O(m + n) | Tracks row and column parity only |
Algorithm Walkthrough
- Create two arrays:
row_parityof sizemcol_parityof sizen
Each value represents whether that row or column has been incremented an odd number of times. We can store this as 0 for even and 1 for odd.
2. Process every operation [ri, ci] in indices.
For each operation:
- Toggle
row_parity[ri] - Toggle
col_parity[ci]
We toggle because every increment changes parity:
- even becomes odd
- odd becomes even
This can be done efficiently using XOR with 1.
3. Initialize a counter called odd_count.
4. Traverse every cell (r, c) in the matrix.
For each cell:
- Compute
row_parity[r] + col_parity[c] - If the sum is odd, increment
odd_count
This works because:
0 + 1 = 1, odd1 + 0 = 1, odd0 + 0 = 0, even1 + 1 = 2, even
- Return
odd_count.
Why it works
Each operation contributes exactly one increment to all cells in a specific row and all cells in a specific column. The final value of a cell depends only on how many times its row and column were incremented.
Parity completely determines whether a number is odd or even. Since adding two odd counts produces an even result, and adding one odd and one even produces an odd result, tracking parity alone is sufficient to determine the final answer correctly.
Python Solution
from typing import List
class Solution:
def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
row_parity = [0] * m
col_parity = [0] * n
for row, col in indices:
row_parity[row] ^= 1
col_parity[col] ^= 1
odd_count = 0
for row in range(m):
for col in range(n):
if (row_parity[row] + col_parity[col]) % 2 == 1:
odd_count += 1
return odd_count
The implementation begins by creating two arrays to track the parity state of each row and column. Instead of storing full increment counts, we only store whether the number of increments is currently odd or even.
While processing indices, the code toggles the corresponding row and column values using XOR. XOR with 1 is a convenient way to flip between 0 and 1.
After all operations are processed, the solution iterates through every matrix position. For each cell, it checks whether the sum of the row parity and column parity is odd. If so, that cell contributes to the answer.
The solution avoids constructing the actual matrix entirely, which reduces memory usage and keeps the logic focused on parity.
Go Solution
func oddCells(m int, n int, indices [][]int) int {
rowParity := make([]int, m)
colParity := make([]int, n)
for _, index := range indices {
row := index[0]
col := index[1]
rowParity[row] ^= 1
colParity[col] ^= 1
}
oddCount := 0
for row := 0; row < m; row++ {
for col := 0; col < n; col++ {
if (rowParity[row]+colParity[col])%2 == 1 {
oddCount++
}
}
}
return oddCount
}
The Go implementation follows the same logic as the Python version. Slices are used instead of Python lists to track row and column parity.
Go does not require special handling for integer overflow here because all values remain very small. Empty versus nil slices are also irrelevant because the problem guarantees valid input sizes and at least one operation.
Worked Examples
Example 1
Input:
m = 2
n = 3
indices = [[0,1],[1,1]]
Initial parity arrays:
| Row | row_parity |
|---|---|
| 0 | 0 |
| 1 | 0 |
| Column | col_parity |
|---|---|
| 0 | 0 |
| 1 | 0 |
| 2 | 0 |
Process [0,1]:
- Toggle row
0 - Toggle column
1
Updated state:
| Row | row_parity |
|---|---|
| 0 | 1 |
| 1 | 0 |
| Column | col_parity |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 0 |
Process [1,1]:
- Toggle row
1 - Toggle column
1
Updated state:
| Row | row_parity |
|---|---|
| 0 | 1 |
| 1 | 1 |
| Column | col_parity |
|---|---|
| 0 | 0 |
| 1 | 0 |
| 2 | 0 |
Now evaluate every cell:
| Cell | Calculation | Odd? |
|---|---|---|
| (0,0) | 1 + 0 = 1 | Yes |
| (0,1) | 1 + 0 = 1 | Yes |
| (0,2) | 1 + 0 = 1 | Yes |
| (1,0) | 1 + 0 = 1 | Yes |
| (1,1) | 1 + 0 = 1 | Yes |
| (1,2) | 1 + 0 = 1 | Yes |
Final answer:
6
Example 2
Input:
m = 2
n = 2
indices = [[1,1],[0,0]]
Initial parity arrays:
row_parity = [0, 0]
col_parity = [0, 0]
Process [1,1]:
row_parity = [0, 1]
col_parity = [0, 1]
Process [0,0]:
row_parity = [1, 1]
col_parity = [1, 1]
Evaluate cells:
| Cell | Calculation | Odd? |
|---|---|---|
| (0,0) | 1 + 1 = 2 | No |
| (0,1) | 1 + 1 = 2 | No |
| (1,0) | 1 + 1 = 2 | No |
| (1,1) | 1 + 1 = 2 | No |
Final answer:
0
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(indices.length + m × n) | Processing operations plus checking every cell |
| Space | O(m + n) | Stores parity arrays for rows and columns |
The algorithm processes each operation exactly once while updating row and column parity arrays. Afterward, it scans all matrix positions to determine whether each cell is odd or even.
The space usage is efficient because we never allocate the full matrix. Instead, we only store parity information for rows and columns.
Test Cases
from typing import List
class Solution:
def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
row_parity = [0] * m
col_parity = [0] * n
for row, col in indices:
row_parity[row] ^= 1
col_parity[col] ^= 1
odd_count = 0
for row in range(m):
for col in range(n):
if (row_parity[row] + col_parity[col]) % 2 == 1:
odd_count += 1
return odd_count
solution = Solution()
assert solution.oddCells(2, 3, [[0, 1], [1, 1]]) == 6 # Provided example 1
assert solution.oddCells(2, 2, [[1, 1], [0, 0]]) == 0 # Provided example 2
assert solution.oddCells(1, 1, [[0, 0]]) == 0 # Single cell incremented twice
assert solution.oddCells(1, 2, [[0, 0]]) == 1 # One odd cell in single row
assert solution.oddCells(2, 1, [[0, 0]]) == 1 # One odd cell in single column
assert solution.oddCells(3, 3, [[0, 0], [0, 0]]) == 0 # Repeated operations cancel parity
assert solution.oddCells(2, 3, [[0, 1]]) == 4 # One operation affects row and column
assert solution.oddCells(3, 4, [[1, 2], [1, 2], [1, 2]]) == 5 # Odd number of repeated operations
assert solution.oddCells(50, 50, [[0, 0]]) == 98 # Large matrix boundary case
| Test | Why |
|---|---|
2x3 with [[0,1],[1,1]] |
Validates provided example with all odd cells |
2x2 with [[1,1],[0,0]] |
Validates provided example with no odd cells |
1x1 with [[0,0]] |
Tests smallest possible matrix |
1x2 with [[0,0]] |
Tests single row behavior |
2x1 with [[0,0]] |
Tests single column behavior |
| Repeated identical operations | Verifies parity cancellation |
| Single operation case | Confirms row and column interaction |
| Triple repeated operation | Confirms odd repetition handling |
50x50 matrix |
Tests upper constraint boundary |
Edge Cases
One important edge case is a 1 x 1 matrix. In this situation, incrementing row 0 and column 0 affects the same single cell twice. A naive implementation might incorrectly count this as odd because it sees two operations affecting the cell independently. The implementation handles this correctly because parity is determined by the total increment count, and 2 is even.
Another important case is repeated operations on the same row and column. For example, applying [0,0] twice should cancel out the parity changes entirely. The XOR toggling logic naturally handles this because toggling twice returns the parity back to even.
A third important edge case occurs when only rows or only columns effectively contribute odd parity. For example, if every column is toggled an even number of times but some rows are toggled oddly, then every cell in those rows becomes odd. The implementation correctly evaluates each cell using the combined parity of its row and column.
A final subtle case involves overlapping increments. Every operation increments one entire row and one entire column, meaning the intersection cell receives two increments during that operation. A direct simulation handles this naturally, but parity-based solutions can accidentally miscount if they do not properly combine row and column parity. The formula (row_parity[row] + col_parity[col]) % 2 guarantees correct handling of this overlap.