Cells with Odd Values in a Matrix - Solution & Explanation
Problem Statement
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?
Approach Overview
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 1: Brute Force Approach
The brute force approach involves directly simulating the incrementation of rows and columns. Start by initializing the matrix to 0, then iterate through each index pair in the indices array, incrementing the values of the specified row and column. Finally, count the number of odd values in the resultant matrix.
The C solution initializes a matrix and iterates over each index in the indices array to increment the specified row and column. It then counts and returns the number of odd values.
Complexity
Time complexity: O(m * n + k * (m + n))
Space complexity: O(m * n)
Approach 2: Optimized Counting Approach
This approach focuses on tracking the number of increments for each row and column separately, rather than incrementing the matrix directly. We use two arrays to count the number of times each row and each column is incremented. Finally, we calculate the number of odd values based on these counts.
This C solution counts the increments for rows and columns without directly modifying the matrix. It calculates if the sum of the row and column increments is odd, updating a count of odd cells as needed.
Complexity
Time complexity: O(m + n + k)
Space complexity: O(m + n)
Approach 3: Simulation
We create a matrix g to store the result of operations. For each pair (r_i, c_i) in indices, we add 1 to all numbers in the r_i-th row of the matrix and add 1 to all elements in the c_i-th column.
After the simulation ends, we traverse the matrix and count the number of odd numbers.
The time complexity is O(k times (m + n) + m times n), and the space complexity is O(m times n). Here, k is the length of indices.
Approach 4: Space Optimization
We can use a row array row and a column array col to record the number of times each row and column is incremented. For each pair (r_i, c_i) in indices, we add 1 to row[r_i] and col[c_i] respectively.
After the operations are completed, the count at position (i, j) can be calculated as row[i] + col[j]. We traverse the matrix and count the number of odd numbers.
The time complexity is O(k + m times n), and the space complexity is O(m + n). Here, k is the length of indices.
Approach 5: Mathematical Optimization
We notice that a number at position (i, j) in the matrix will be odd only when exactly one of row[i] and col[j] is odd and the other is even.
We count the number of odd numbers in row, denoted as cnt1, and the number of odd numbers in col, denoted as cnt2. Therefore, the final count of odd numbers is cnt1 times (n - cnt2) + cnt2 times (m - cnt1).
The time complexity is O(k + m + n), and the space complexity is O(m + n). Here, k is the length of indices.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time complexity: O(m * n + k * (m + n)) |
| Optimized Counting Approach | Time complexity: O(m + n + k) |
| Simulation | — |
| Space Optimization | — |
| Mathematical Optimization | — |
Detailed Complexity Analysis
| 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 |
Video Solution
1252. Cells with Odd Values in a Matrix | Zero to FAANG Kunal | Assignment Solution | Leetcode • Programmers Zone • 10,467 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Cells with Odd Values in a Matrix easy or hard?
Cells with Odd Values in a Matrix Python/Java solution
How to solve Cells with Odd Values in a Matrix in O(n)?
What is the best approach for Cells with Odd Values in a Matrix?
Is Cells with Odd Values in a Matrix asked at Google/Amazon/Meta?
What data structure is used in Cells with Odd Values in a Matrix?
What is the time complexity of Cells with Odd Values in a Matrix?
Ready to solve this problem?
Practice Cells with Odd Values in a Matrix with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor