Cells with Odd Values in a Matrix

EASY

Description

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] = [r_i, c_i] 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 r_i.
Increment all the cells on column c_i.

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 <= 50
1 <= indices.length <= 100
0 <= r_i < m
0 <= c_i < n

Follow up: Could you solve this in O(n + m + indices.length) time with only O(n + m) extra space?

Approaches

Checkout 3 different approaches to solve Cells with Odd Values in a Matrix. Click on different approaches to view the approach and algorithm in detail.

Auxiliary Arrays with Brute-Force Count

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_counts of size m, initialized to zeros.
Create an integer array col_counts of size n, initialized to zeros.
Iterate through each pair [r, c] in the indices array:
- Increment row_counts[r].
- Increment col_counts[c].
Initialize a counter odd_count to 0.
Iterate from i = 0 to m-1 and j = 0 to n-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 value is odd, increment odd_count.
Return odd_count.

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 Analysis

Time Complexity: O(indices.length + m * n). We iterate through `indices` once, and then we iterate through all `m * n` conceptual cells.Space Complexity: O(m + n) for the two auxiliary arrays.

Pros and Cons

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 * n cells, which can be slow if m and n are large.

Code Solutions

Checking out 3 solutions in different languages for Cells with Odd Values in a Matrix. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Cells with Odd Values in a Matrix

Patterns:

Math

Data Structures:

Array