Problem

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

  1. Increment all the cells on row ri.
  2. Increment all the cells on column ci.

Given m, n, and indices, return _thenumber of odd-valued cells in the matrix after applying the increment to all locations in _indices.

Examples

Example 1

1
2
3
4
5

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

Example 2

1
2
3

Input: m = 2, n = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]]. There are no odd numbers in the final matrix.

Constraints

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

Follow up: Could you solve this in O(n + m + indices.length) time with only O(n + m) extra space?

Solution

Method 1 – Row and Column Parity Counting

Intuition: Instead of simulating the entire matrix, we can just count how many times each row and column is incremented. The parity (odd/even) of the sum of increments for each cell determines if it’s odd. This is much more efficient than updating the matrix directly.

Approach:

  1. Initialize two arrays: one for row increments and one for column increments.
  2. For each index in indices, increment the corresponding row and column counters.
  3. For each cell, its value is odd if the sum of its row and column increments is odd.
  4. Count and return the number of such cells.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[] row = new int[m];
        int[] col = new int[n];
        for (int[] idx : indices) {
            row[idx[0]]++;
            col[idx[1]]++;
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((row[i] + col[j]) % 2 == 1) ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def oddCells(self, m: int, n: int, indices: list[list[int]]) -> int:
        row = [0] * m
        col = [0] * n
        for r, c in indices:
            row[r] += 1
            col[c] += 1
        ans = 0
        for i in range(m):
            for j in range(n):
                if (row[i] + col[j]) % 2 == 1:
                    ans += 1
        return ans

Complexity

  • ⏰ Time complexity: O(m + n + len(indices))
  • 🧺 Space complexity: O(m + n)