Problem Description

You are given an m x n matrix that starts with all cells containing 0. You also have a 2D array called indices, where each element indices[i] = [ri, ci] represents a row index ri and a column index ci.

For each pair [ri, ci] in the indices array, you need to perform two operations:

1. Add 1 to every cell in row ri (increment all cells in that entire row)
2. Add 1 to every cell in column ci (increment all cells in that entire column)

After performing all these increment operations for every pair in indices, your task is to count how many cells in the final matrix contain odd values.

For example, if you have a 2×3 matrix and indices = [[0,1], [1,1]]:

• For [0,1]: increment all cells in row 0 and all cells in column 1
• For [1,1]: increment all cells in row 1 and all cells in column 1
• Column 1 gets incremented twice (once for each operation), while other positions get incremented based on their row/column involvement

The solution simulates this process by creating a matrix g and applying each increment operation. For each [r, c] pair, it adds 1 to all cells in row r and all cells in column c. Finally, it counts the cells with odd values using the modulo operator (v % 2).

Intuition

The key insight is to recognize that this is a straightforward simulation problem. Since we need to track how many times each cell gets incremented, the most direct approach is to actually perform the operations and count the results.

When we see an operation [r, c], every cell in row r gets incremented by 1, and every cell in column c gets incremented by 1. Notice that the cell at position [r, c] gets incremented twice - once from the row operation and once from the column operation.

To determine if a cell's final value is odd, we need to know the total number of increments it received. A cell that starts at 0 will be odd if it's incremented an odd number of times, and even if it's incremented an even number of times.

The simulation approach is natural here because:

1. The constraints are manageable (matrix size and number of operations are not too large)
2. We need the exact count for each cell to determine oddness
3. Each operation affects multiple cells, making it easier to just apply the operations rather than trying to calculate the effect analytically

After all operations are complete, we simply check each cell's value modulo 2. If value % 2 == 1, the cell contains an odd number, and we count it. This gives us our final answer.

Learn more about Math patterns.

Solution Approach

The solution uses a simulation approach with a 2D list to track all increments.

Step 1: Initialize the Matrix
We create a 2D list g with dimensions m x n, initialized with all zeros:

g = [[0] * n for _ in range(m)]

This represents our matrix that will store the cumulative increments.

Step 2: Process Each Index Pair
For each pair [r, c] in indices, we perform two operations:

• Row Increment: Add 1 to all cells in row r

  for j in range(n):
      g[r][j] += 1

• Column Increment: Add 1 to all cells in column c

  for i in range(m):
      g[i][c] += 1

Note that the cell at position [r, c] gets incremented twice - once from each operation.

Step 3: Count Odd Values
After processing all index pairs, we count the cells with odd values using a generator expression:

return sum(v % 2 for row in g for v in row)

This flattens the 2D matrix and checks each value. The expression v % 2 returns 1 if v is odd and 0 if even, so summing these gives us the total count of odd cells.

Time Complexity: O(k × (m + n)) where k is the length of indices, as each index pair requires iterating through one row and one column.

Space Complexity: O(m × n) for storing the matrix g.

Example Walkthrough

Let's walk through a small example with a 2×3 matrix and indices = [[0,1], [1,1]].

Initial Setup:

• Matrix dimensions: m = 2, n = 3
• Starting matrix g:

[0, 0, 0]
[0, 0, 0]

Processing First Index Pair [0,1]:

Row operation (increment all cells in row 0):

[1, 1, 1]  ← row 0 incremented
[0, 0, 0]

Column operation (increment all cells in column 1):

[1, 2, 1]
[0, 1, 0]
    ↑
 column 1 incremented

Notice cell [0,1] was incremented twice (once for row, once for column).

Processing Second Index Pair [1,1]:

Row operation (increment all cells in row 1):

[1, 2, 1]
[1, 2, 1]  ← row 1 incremented

Column operation (increment all cells in column 1):

[1, 3, 1]
[1, 3, 1]
    ↑
 column 1 incremented

Final Count: Matrix after all operations:

[1, 3, 1]
[1, 3, 1]

Checking each cell for odd values:

• Position [0,0]: value = 1 (odd) ✓
• Position [0,1]: value = 3 (odd) ✓
• Position [0,2]: value = 1 (odd) ✓
• Position [1,0]: value = 1 (odd) ✓
• Position [1,1]: value = 3 (odd) ✓
• Position [1,2]: value = 1 (odd) ✓

Total odd cells: 6

The key observation is that each cell's final value equals the number of times it was incremented. Cell [0,1] was incremented 3 times total: twice from the first index pair (being at the intersection) and once more from the second pair's column operation.

Solution Implementation

Time and Space Complexity

Time Complexity: O(k × (m + n) + m × n)

The time complexity breaks down into two main parts:

• The first part O(k × (m + n)) comes from iterating through the indices array of length k. For each index pair (r, c):
  • We iterate through all m rows to increment column c: O(m)
  • We iterate through all n columns to increment row r: O(n)
  • Total for each index: O(m + n)
  • For all k indices: O(k × (m + n))
• The second part O(m × n) comes from the final counting step where we iterate through all m × n cells in the grid to count odd values

Therefore, the total time complexity is O(k × (m + n) + m × n).

Space Complexity: O(m × n)

The space complexity is dominated by the 2D grid g that we create with dimensions m × n. This grid stores the count for each cell, requiring O(m × n) space. The additional variables used (loop counters, temporary variables) only require O(1) extra space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Double Counting at Intersection Points

A common misconception is thinking that the cell at position [r, c] should only be incremented once. In reality, it gets incremented twice - once during the row increment and once during the column increment. Some might try to "fix" this by skipping the intersection point:

Incorrect approach:

# Wrong - trying to avoid "double counting"
for j in range(n):
    if j != c:  # This is wrong!
        matrix[r][j] += 1
for i in range(m):
    if i != r:  # This is wrong!
        matrix[i][c] += 1
matrix[r][c] += 1  # Add once for the intersection

Why this is wrong: The problem specifically states to increment ALL cells in the row and ALL cells in the column. The intersection naturally gets both increments.

2. Memory-Inefficient Solution for Large Matrices

Creating a full m x n matrix can be memory-intensive when dimensions are large. A more efficient approach tracks only row and column increment counts:

Optimized Solution:

def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
    row_counts = [0] * m
    col_counts = [0] * n
  
    # Count increments for each row and column
    for r, c in indices:
        row_counts[r] += 1
        col_counts[c] += 1
  
    # Count cells with odd values
    odd_count = 0
    for i in range(m):
        for j in range(n):
            if (row_counts[i] + col_counts[j]) % 2 == 1:
                odd_count += 1
  
    return odd_count

This reduces space complexity from O(m × n) to O(m + n).

3. Confusion About Order of Operations

Some might think the order of processing indices matters or that increments should be applied simultaneously. The order doesn't matter because addition is commutative - the final count at each cell will be the same regardless of processing order.

4. Off-by-One Errors in Loop Ranges

Ensure loops use range(m) and range(n) correctly. Common mistakes include using range(m-1) or confusing which dimension corresponds to rows vs columns.