Cells with Odd Values in a Matrix
EasyPrompt
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:
- Increment all the cells on row
ri. - Increment all the cells on column
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?
Approaches
3 approaches with complexity analysis and trade-offs.
This approach avoids building the full matrix. It observes that the final value of a cell (r, c) is the sum of increments for row r and column c. We can use two auxiliary arrays to store the total number of times each row and column is incremented. Then, we can calculate the final value for each cell and check its parity.
Algorithm
- Create an integer array
row_countsof sizem, initialized to zeros. - Create an integer array
col_countsof sizen, initialized to zeros. - Iterate through each pair
[r, c]in theindicesarray:- Increment
row_counts[r]. - Increment
col_counts[c].
- Increment
- Initialize a counter
odd_countto 0. - Iterate from
i = 0tom-1andj = 0ton-1(conceptually iterating through the matrix cells). - For each pair
(i, j), calculate the final cell value:value = row_counts[i] + col_counts[j]. - If
valueis odd, incrementodd_count. - Return
odd_count.
Walkthrough
Instead of simulating the matrix operations directly, we can optimize by realizing that the final value of any cell matrix[i][j] is simply the sum of the number of times its row i was incremented and the number of times its column j was incremented. This allows us to avoid constructing the m x n matrix. We can use two separate arrays, one to keep track of the increment counts for each row and another for each column. After populating these count arrays by iterating through indices, we can then iterate through all m * n conceptual cell positions, calculate the final value for each, and count how many are odd.
class Solution { public int oddCells(int m, int n, int[][] indices) { int[] rowCounts = new int[m]; int[] colCounts = new int[n]; for (int[] index : indices) { rowCounts[index[0]]++; colCounts[index[1]]++; } int oddCount = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if ((rowCounts[i] + colCounts[j]) % 2 != 0) { oddCount++; } } } return oddCount; }}Complexity
Time
O(indices.length + m * n). We iterate through `indices` once, and then we iterate through all `m * n` conceptual cells.
Space
O(m + n) for the two auxiliary arrays.
Trade-offs
Pros
More space-efficient than the simulation approach.
Time complexity is improved by avoiding repeated traversals of rows and columns.
Cons
The final counting step still requires iterating through
m * ncells, which can be slow ifmandnare large.
Solutions
Solution
class Solution {public int oddCells(int m, int n, int[][] indices) { int[][] g = new int[m][n]; for (int[] e : indices) { int r = e[0], c = e[1]; for (int i = 0; i < m; ++i) { g[i][c]++; } for (int j = 0; j < n; ++j) { g[r][j]++; } } int ans = 0; for (int[] row : g) { for (int v : row) { ans += v % 2; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.