Cells with Odd Values in a Matrix

Difficulty: Easy | Acceptance: 79.80% | Paid: No Topics: Array, Math, Simulation

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 the following:

Increment all the cells on row ri. 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.

• Examples
• Constraints
• Brute Force Simulation
• Mathematical Approach

Examples

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 = [[1,2,1],[0,1,0]].
The final matrix is [[1,3,1],[1,3,1]], which contains 6 odd numbers.

Input: m = 2, n = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]], which contains 0 odd numbers.

Constraints

1 <= m, n <= 50
1 <= indices.length <= 100
0 <= ri < m
0 <= ci < n

Brute Force Simulation

Intuition Simulate each operation directly by creating the matrix and incrementing cells row by row and column by column, then count odd values.

Steps

• Initialize an m x n matrix with all zeros
• For each [ri, ci] in indices, increment all cells in row ri and column ci
• Count all cells with odd values and return the count

class Solution:
    def oddCells(self, m: int, n: int, indices: list[list[int]]) -> int:
        matrix = [[0] * n for _ in range(m)]
        for ri, ci in indices:
            for j in range(n):
                matrix[ri][j] += 1
            for i in range(m):
                matrix[i][ci] += 1
        count = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] % 2 == 1:
                    count += 1
        return count

Complexity

• Time: O(k × (m + n) + m × n) where k is the length of indices
• Space: O(m × n)
• Notes: Simple to understand but uses extra space for the matrix

Mathematical Approach

Intuition A cell (i, j) is odd when the sum of operations on row i and column j is odd. This happens when one count is odd and the other is even.

Steps

• Count how many times each row and column is incremented
• Count odd rows and odd columns
• Result = (odd rows × even columns) + (even rows × odd columns)

class Solution:
    def oddCells(self, m: int, n: int, indices: list[list[int]]) -> int:
        row_ops = [0] * m
        col_ops = [0] * n
        for ri, ci in indices:
            row_ops[ri] += 1
            col_ops[ci] += 1
        
        odd_rows = sum(1 for x in row_ops if x % 2 == 1)
        even_rows = m - odd_rows
        odd_cols = sum(1 for x in col_ops if x % 2 == 1)
        even_cols = n - odd_cols
        
        return odd_rows * even_cols + even_rows * odd_cols

Complexity

• Time: O(k + m + n) where k is the length of indices
• Space: O(m + n)
• Notes: Optimal solution with minimal space complexity