Cells with Odd Values in a Matrix

Problem 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:

1. Increment all the cells on row r_i.
2. 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.

Key Insights

• The matrix starts with all values set to zero.
• Each operation increments an entire row and an entire column, which can lead to multiple increments at the same cell.
• The parity (odd/even nature) of a cell can be determined by the total number of increments applied to it.
• To efficiently count odd values, we can track the number of increments for each row and each column separately rather than manipulating the actual matrix.

Space and Time Complexity

Time Complexity: O(m + n + indices.length)
Space Complexity: O(m + n)

Solution

The solution leverages two arrays to count the number of increments for each row and each column. We increment the relevant row and column counters based on the indices provided. After processing all indices, we can compute the total number of odd-valued cells by checking the parity of the sum of increments for each cell position derived from the row and column counters.

Code Solutions