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.
This approach directly simulates the process described in the problem. It involves creating an m x n matrix, iterating through each index pair in indices to increment the corresponding rows and columns, and finally, traversing the entire matrix to count the cells with odd values.
Algorithm
- Initialize an
m x ninteger matrix,matrix, with all elements set to 0. - Iterate through each pair
[r, c]in theindicesarray. - For each
[r, c], perform two sub-steps:- Increment every element in row
r: Iterate fromj = 0ton-1and incrementmatrix[r][j]. - Increment every element in column
c: Iterate fromi = 0tom-1and incrementmatrix[i][c].
- Increment every element in row
- Initialize a counter
odd_countto 0. - Iterate through the entire
matrixfromi = 0tom-1andj = 0ton-1. - For each cell
matrix[i][j], check if its value is odd (i.e.,matrix[i][j] % 2 != 0). - If the value is odd, increment
odd_count. - Return
odd_count.
Walkthrough
The most straightforward way to solve the problem is to follow the instructions literally. We create a 2D array that represents the matrix and initialize it with zeros. Then, for each entry in the indices array, we iterate through the specified row and column, incrementing each cell's value. After all increment operations are complete, we perform a final pass over the entire matrix to count how many cells contain an odd number.
class Solution { public int oddCells(int m, int n, int[][] indices) { int[][] matrix = new int[m][n]; for (int[] index : indices) { int r = index[0]; int c = index[1]; // Increment row r for (int j = 0; j < n; j++) { matrix[r][j]++; } // Increment column c for (int i = 0; i < m; i++) { matrix[i][c]++; } } int oddCount = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] % 2 != 0) { oddCount++; } } } return oddCount; }}Complexity
Time
O(indices.length * (m + n) + m * n). For each of the `indices.length` operations, we traverse a row of `n` elements and a column of `m` elements. After all operations, we traverse the `m * n` matrix to count odd cells.
Space
O(m * n) to store the matrix.
Trade-offs
Pros
Simple to understand and implement as it directly follows the problem statement.
Cons
Inefficient in both time and space, especially for large matrices.
The space complexity of O(m * n) can be prohibitive if m and n are large.
This is the most efficient approach. It builds upon the previous idea but optimizes the final counting step. A cell (r, c) has an odd value if row_counts[r] + col_counts[c] is odd. This happens if one count is odd and the other is even. Instead of checking every cell, we can count the number of rows with odd increments (odd_rows) and columns with odd increments (odd_cols). The total number of odd cells is then odd_rows * even_cols + even_rows * odd_cols.
Algorithm
- Create a boolean array
row_is_oddof sizemandcol_is_oddof sizen, initialized tofalse. These will track the parity of increments for each row and column. - Iterate through each pair
[r, c]in theindicesarray:- Flip the boolean value:
row_is_odd[r] = !row_is_odd[r]. - Flip the boolean value:
col_is_odd[c] = !col_is_odd[c].
- Flip the boolean value:
- Count the number of rows with an odd number of increments. Initialize
odd_rows_count = 0. Iterate throughrow_is_odd, and ifrow_is_odd[i]istrue, incrementodd_rows_count. - Count the number of columns with an odd number of increments. Initialize
odd_cols_count = 0. Iterate throughcol_is_odd, and ifcol_is_odd[j]istrue, incrementodd_cols_count. - The number of rows with an even number of increments is
even_rows_count = m - odd_rows_count. - The number of columns with an even number of increments is
even_cols_count = n - odd_cols_count. - A cell
(i, j)is odd if its row increment count is odd and column is even, OR its row is even and column is odd. - Calculate the total number of odd cells:
result = (odd_rows_count * even_cols_count) + (even_rows_count * odd_cols_count). - Return
result.
Walkthrough
This approach further optimizes the previous one by eliminating the O(m * n) loop. We only need to know the parity (odd or even) of the increment counts, not their exact values. A cell (i, j) will have an odd value if row_counts[i] is odd and col_counts[j] is even, or vice versa.
We can first determine the parity for all row and column increments. We use two boolean arrays, oddRows and oddCols, to track this. After iterating through indices and flipping the boolean flags, we count the total number of rows with odd increments (oddRowCount) and columns with odd increments (oddColCount). The number of rows and columns with even increments are then m - oddRowCount and n - oddColCount respectively. The final answer is the number of cells in odd-increment rows and even-increment columns, plus the number of cells in even-increment rows and odd-increment columns. This can be calculated with a simple formula, avoiding the nested loops entirely.
class Solution { public int oddCells(int m, int n, int[][] indices) { boolean[] oddRows = new boolean[m]; boolean[] oddCols = new boolean[n]; for (int[] index : indices) { oddRows[index[0]] = !oddRows[index[0]]; oddCols[index[1]] = !oddCols[index[1]]; } int oddRowCount = 0; for (int i = 0; i < m; i++) { if (oddRows[i]) { oddRowCount++; } } int oddColCount = 0; for (int j = 0; j < n; j++) { if (oddCols[j]) { oddColCount++; } } int evenRowCount = m - oddRowCount; int evenColCount = n - oddColCount; return oddRowCount * evenColCount + evenRowCount * oddColCount; }}Complexity
Time
O(indices.length + m + n). We iterate through `indices` once (`O(indices.length)`), then through the row parities (`O(m)`), and then the column parities (`O(n)`).
Space
O(m + n) for the two boolean arrays.
Trade-offs
Pros
Highly efficient in both time and space.
It avoids the O(m * n) complexity entirely, making it suitable for large matrices.
Satisfies the follow-up constraints of the problem.
Cons
The logic is slightly more abstract than the direct simulation, which might make it harder to come up with initially.
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; }}class Solution {public: int oddCells(int m, int n, vector<vector<int>> &indices) { vector<vector<int>> g(m, vector<int>(n)); for (auto &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 (auto &row : g) for (int v : row) ans += v % 2; return ans; }};class Solution: def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int: g = [[0] * n for _ in range(m)] for r, c in indices: for i in range(m): g[i][c] += 1 for j in range(n): g[r][j] += 1 return sum(v % 2 for row in g for v in row)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.