Cells with Odd Values in a Matrix

easy matrix parity simulation

Problem

You are given m and n, the dimensions of a matrix filled with zeros, and a list of indices. For each pair [r, c] in indices, increment every cell in row r by 1 and every cell in column c by 1. Return how many cells of the final matrix contain an odd value.

Inputm = 2, n = 3, indices = [[0, 1], [1, 1]]

Output6

After both operations the matrix is [[1, 3, 1], [1, 3, 1]] — all 6 cells are odd.

m (rows)

n (cols)

indices (e.g. [0,1],[1,1])

def odd_cells(m, n, indices):
    rows = [0] * m
    cols = [0] * n
    for r, c in indices:
        rows[r] += 1
        cols[c] += 1
    odd = 0
    for i in range(m):
        for j in range(n):
            if (rows[i] + cols[j]) % 2 == 1:
                odd += 1
    return odd

function oddCells(m, n, indices) {
  const rows = new Array(m).fill(0);
  const cols = new Array(n).fill(0);
  for (const [r, c] of indices) {
    rows[r] += 1;
    cols[c] += 1;
  }
  let odd = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if ((rows[i] + cols[j]) % 2 === 1) odd++;
    }
  }
  return odd;
}

class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[] rows = new int[m];
        int[] cols = new int[n];
        for (int[] p : indices) {
            rows[p[0]]++;
            cols[p[1]]++;
        }
        int odd = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (((rows[i] + cols[j]) & 1) == 1) odd++;
            }
        }
        return odd;
    }
}

int oddCells(int m, int n, vector<vector<int>>& indices) {
    vector<int> rows(m, 0), cols(n, 0);
    for (auto& p : indices) {
        rows[p[0]]++;
        cols[p[1]]++;
    }
    int odd = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (((rows[i] + cols[j]) & 1) == 1) odd++;
    return odd;
}

Explanation

Instead of building the whole matrix and bumping lots of cells, we just count how many times each row and each column got incremented. A cell's final value is simply rows[i] + cols[j].

This works because every operation [r, c] adds 1 to an entire row and an entire column. So the value at cell (i, j) only depends on how many operations touched row i and how many touched column j — exactly rows[i] + cols[j].

First we walk the operations and tally the counters: rows[r] += 1 and cols[c] += 1. Then we loop over every (i, j) pair and check if (rows[i] + cols[j]) % 2 == 1, counting the odd ones.

Example: m = 2, n = 3, indices = [[0,1],[1,1]]. The counters become rows = [1, 1] and cols = [0, 2, 0]. Cell sums are 1, 3, 1 in both rows, and all six are odd, so the answer is 6.

The neat part is we never store the matrix itself — only two small arrays of row and column counts, which is much lighter on memory.

Time: O(m·n + k) Space: O(m + n)