Watch 10 video solutions for Cells with Odd Values in a Matrix, a easy level problem involving Array, Math, Simulation. This walkthrough by Programmers Zone has 10,242 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
ri.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.
Example 1:
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:
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 <= 501 <= indices.length <= 1000 <= ri < m0 <= ci < n
Follow up: Could you solve this in O(n + m + indices.length) time with only O(n + m) extra space?
Problem Overview: You start with an m x n matrix filled with zeros. For every pair [ri, ci] in indices, increment all cells in row ri and column ci. After applying all operations, count how many cells contain odd values.
Approach 1: Brute Force Simulation (Time: O(k*(m+n) + m*n), Space: O(m*n))
Create the full matrix and directly simulate every operation. For each index pair [r, c], iterate across the entire row r and increment each column value, then iterate down column c and increment each row value. After processing all operations, iterate through the matrix and count cells where value % 2 == 1. This approach mirrors the problem statement exactly and is easy to implement. It relies on straightforward simulation with nested loops, but the matrix allocation and repeated updates make it inefficient for larger dimensions.
Approach 2: Optimized Counting with Row/Column Parity (Time: O(k + m + n), Space: O(m+n))
The key observation: the actual values do not matter, only whether the number of increments applied to a cell is odd or even. Track how many times each row and column is incremented using two arrays: row[m] and col[n]. For every operation [r, c], increment row[r] and col[c]. A cell (i, j) becomes odd if (row[i] + col[j]) % 2 == 1. Instead of checking every cell individually, count how many rows have odd increments and how many columns have odd increments. The final number of odd cells is oddRows * (n - oddCols) + (m - oddRows) * oddCols. This works because an odd row combined with an even column produces an odd cell, and vice versa. The solution uses simple array counting and a small piece of math to avoid scanning the entire matrix.
Recommended for interviews: The optimized counting approach is what interviewers expect. It shows you recognize that only parity matters and avoid unnecessary simulation. Implementing the brute force first demonstrates understanding of the operations, but reducing the problem to row/column parity proves stronger algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(k*(m+n) + m*n) | O(m*n) | When learning the problem or when matrix dimensions are small |
| Optimized Row/Column Counting | O(k + m + n) | O(m+n) | Best approach for interviews and large inputs where full simulation is unnecessary |