LeetCode 1252: Cells with Odd Values in a Matrix

Explanation

To solve this problem efficiently, we can keep track of the count of increments along rows and columns separately. Then, we can iterate through the indices and update the counts accordingly. Finally, we can calculate the number of odd-valued cells in the matrix based on the counts.

1. Initialize variables to store rowCounts and colCounts.
2. Iterate through the indices and update the rowCounts and colCounts based on the increments.
3. Calculate the number of odd-valued cells in the matrix.
4. Return the count of odd-valued cells.

Time complexity: O(n + m + indices.length) - we iterate through the matrix once and through the indices array once. Space complexity: O(n + m) - we store the counts of increments along rows and columns.

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 == 1) {
                    oddCount++;
                }
            }
        }
        
        return oddCount;
    }
}