Code Logo

Cells with Odd Values in a Matrix

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Cells with Odd Values in a Matrix

Solution Approach

Track row and col counts. Count odd rows and odd cols. Use formula to compute odd cells.

function solution(n, m, indices) {
  var rows = new Array(n).fill(0);
  var cols = new Array(m).fill(0);
  for (var i = 0; i < indices.length; i++) {
    rows[indices[i][0]]++;
    cols[indices[i][1]]++;
  }
  var or = 0, oc = 0;
  for (var i = 0; i < n; i++) if (rows[i] % 2 === 1) or++;
  for (var i = 0; i < m; i++) if (cols[i] % 2 === 1) oc++;
  return or * m + oc * n - 2 * or * oc;
}

Time O(n+m+k), Space 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;
    }
}