Code Logo

Cells with Odd Values in a Matrix

Published at24 Jul 2026
Created by
Easy 1 views
Like0

Given n (rows) and m (columns), create a matrix of zeros. Then apply operations from an indices array where each [ri, ci] increments all cells in row ri and all cells in column ci. Return the count of odd-valued cells after all operations.

Instead of simulating the full matrix, track row counts and column counts. Each operation increments a row and a column. The final value at cell (i,j) is rowCounts[i] + colCounts[j]. A cell is odd if this sum is odd.

Track the number of rows with odd count and columns with odd count. The number of odd cells is: oddRows * colCount + oddCols * rowCount - 2 * oddRows * oddCols. Because cells at the intersection of odd rows and odd columns are counted twice and should be even.

Time is O(len(indices)) with O(n + m) space, much better than O(n * m * len(indices)).

The matrix cell parity problem demonstrates how tracking row and column counts avoids simulating the full matrix. The count of odd cells formula uses inclusion-exclusion: oddRows * m + oddCols * n - 2 * oddRows * oddCols accounts for cells counted twice.

The parity tracking approach demonstrates how DP can avoid O(n*m) simulation by using aggregated state variables for rows and columns.

Example Input & Output

Example 1
Input
2, 2, [[1,1],[0,0]]
Output
0
Explanation

All even.

Example 2
Input
1, 2, [[0,0]]
Output
1
Explanation

Cell (0,1) is odd.

Example 3
Input
2, 3, [[0,1],[1,1]]
Output
6
Explanation

6 odd cells.

Example 4
Input
2, 2, [[0,0]]
Output
2
Explanation

Cells (0,1) and (1,0) are odd.

Example 5
Input
1, 1, []
Output
0
Explanation

No ops.

Algorithm Flow

Recommendation Algorithm Flow for Cells with Odd Values in a Matrix

Solution Approach

Given n rows and m columns, perform a series of increment operations on sub-rectangles and count how many cells end up with an odd value. Simulate the operations: create a matrix of zeros, for each operation [r, c], increment all cells in the first r rows and first c columns by 1. After all operations, count odd-valued cells.

function oddCells(n, m, indices) {
  var mat = Array(n).fill(null).map(function() { return Array(m).fill(0); });
  for (var k = 0; k < indices.length; k++) {
    var ri = indices[k][0], ci = indices[k][1];
    for (var r = 0; r < n; r++) mat[r][ci]++;
    for (var c = 0; c < m; c++) mat[ri][c]++;
  }
  var count = 0;
  for (var r = 0; r < n; r++)
    for (var c = 0; c < m; c++)
      if (mat[r][c] % 2 !== 0) count++;
  return count;
}

Each operation increments an entire row and an entire column. The cell at their intersection gets incremented twice, which is equivalent to not changing its parity. Cells along the same row or column as the operation target are incremented once.

Time complexity is O(k * (n + m)), space complexity is O(n * m).

Best Answers

java
class Solution {
    public int solution(int n, int m, int[][] indices) {
        int[] r=new int[n]; int[] c=new int[m];
        for (int[] idx : indices) { r[idx[0]]++; c[idx[1]]++; }
        int or=0,oc=0;
        for (int x:r) if (x%2==1) or++;
        for (int x:c) if (x%2==1) oc++;
        return or*m + oc*n - 2*or*oc;
    }
}