1252. Cells with Odd Values in a Matrix


Problem Description

This LeetCode problem presents an m x n matrix initially filled with all zeroes. We're given a list of indices where each element is a pair [r_i, c_i], indicating a specific row r_i and column c_i in the matrix. For each pair of indices, we need to perform two operations:

  1. Increment all the cells in the specified row r_i.
  2. Increment all the cells in the specified column c_i.

Our goal is to figure out how many cells in the matrix will have odd values after performing all the specified row and column increments.

Intuition

The intuition behind the solution lies in recognizing that we don't actually need to perform all the increments on the entire matrix to find out how many cells will be odd. Instead, we can track the increment counts separately for rows and columns.

We create two lists, row of size m and col of size n, to count how many times each row and each column is incremented. When we process the indices, we increment the corresponding count in row and col arrays for each given pair [r_i, c_i].

After all increments have been tallied, the value of a cell (i, j) in the matrix will be the sum of increments for its row (i.e., row[i]) and its column (i.e., col[j]). If the sum of increments for a cell is odd, then the cell value will be odd. Therefore, the cell will contribute to our final count of odd-valued cells in the matrix.

The code then calculates the total number of odd-valued cells using a simple list comprehension, adding up each possible combination of row[i] and col[j] increments and checking if the result is odd ((i + j) % 2 being 1).

This approach avoids the need for a potentially expensive operation of incrementing every cell in the matrix and instead simplifies the problem to a matter of counting increments per row and column.

Solution Approach

The solution uses a straightforward and efficient approach by utilizing additional data structures to keep track of the number of times each row and column is incremented rather than updating the whole matrix directly. Here's a walkthrough of the implementation steps:

  1. Initialize two arrays row and col with sizes corresponding to the number of rows m and the number of columns n in the matrix, respectively. These will hold the number of times each row and column needs to be incremented.

    1row = [0] * m
    2col = [0] * n
  2. Iterate through each given index in the indices array. For each pair [r_i, c_i], increment the value at position r_i in the row array and the value at position c_i in the col array by 1. This step effectively counts the number of times each row and column should be incremented without actually altering the matrix.

    1for r, c in indices:
    2    row[r] += 1
    3    col[c] += 1
  3. Calculate the number of odd-valued cells. A cell at position (i, j) will have an odd value if the sum of increments from its row and column is odd. To find this, we use a list comprehension that iterates over every possible combination of row and column increments (row[i] + col[j]), and if the sum is odd ((i + j) % 2 == 1), it contributes to the count.

    1return sum((i + j) % 2 for i in row for j in col)

By running through all combinations of row and column increments, the algorithm efficiently calculates the final count of odd-valued cells after performing all specified operations. This solution avoids the time and space complexity issues that would arise from updating the entire matrix after each increment, thereby offering an optimized way to solve the problem.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a small example with a 3x4 matrix (m=3, n=4) and given indices [[0, 1], [1, 1], [2, 2]]. Here's how the solution approach would work with these inputs:

  1. Initialize two arrays row and col to keep track of the increments:

    1row = [0, 0, 0]  # For 3 rows
    2col = [0, 0, 0, 0]  # For 4 columns
  2. Process the given list of indices:

    1indices = [[0, 1], [1, 1], [2, 2]]
    2for r, c in indices:
    3    row[r] += 1
    4    col[c] += 1
    5
    6# After processing the indices, we have:
    7row = [1, 1, 1]  # Row 0, Row 1, and Row 2 are each incremented once
    8col = [0, 2, 1, 0]  # Column 1 is incremented twice and Column 2 once

    Our row and col arrays now represent the total number of times each row and column has been incremented.

  3. Determine the odd-valued cells in the matrix:

    1# A cell (i, j) will be odd if (row[i] + col[j]) is odd.
    2odd_count = sum((row[i] + col[j]) % 2 == 1 for i in range(3) for j in range(4))
    3
    4# Calculate the count:
    5# For i=0 (Row 0): (1+0) % 2, (1+2) % 2, (1+1) % 2, (1+0) % 2  => 1 odd value (at column 1)
    6# For i=1 (Row 1): (1+0) % 2, (1+2) % 2, (1+1) % 2, (1+0) % 2  => 1 odd value (at column 1)
    7# For i=2 (Row 2): (1+0) % 2, (1+2) % 2, (1+1) % 2, (1+0) % 2  => 2 odd values (at columns 1 and 2)
    8# Total odd value count is 4.
    9
    10return odd_count

So, the final count of cells with odd values is 4 for the given example. This method efficiently calculates the odd cell count without modifying the entire matrix, but simply by tracking the number of increments in each row and column.

Python Solution

1class Solution:
2    def oddCells(self, rows: int, cols: int, indices: List[List[int]]) -> int:
3        # Initialize two arrays to track the counts of increments in each row and column,
4        # respectively. Initially, all cells have even counts (0).
5        row_counts = [0] * rows
6        col_counts = [0] * cols
7      
8        # Loop through each pair of indices representing [row, column].
9        # Increment the corresponding row and column count.
10        for r, c in indices:
11            row_counts[r] += 1
12            col_counts[c] += 1
13      
14        # Compute the number of cells with odd values.
15        # For each cell, the value is the sum of the row count and column count.
16        # A cell has an odd value if the sum is an odd number.
17        odd_values_count = sum(
18            (row_count + col_count) % 2
19            for row_count in row_counts
20            for col_count in col_counts
21        )
22      
23        # Return the total count of cells with odd values.
24        return odd_values_count
25

Java Solution

1class Solution {
2    public int oddCells(int m, int n, int[][] indices) {
3        // Create arrays to keep track of the increments for rows and columns
4        int[] rowCount = new int[m];
5        int[] colCount = new int[n];
6      
7        // Increment the corresponding row and column counters for each index pair
8        for (int[] indexPair : indices) {
9            int rowIndex = indexPair[0];
10            int colIndex = indexPair[1];
11            rowCount[rowIndex]++;
12            colCount[colIndex]++;
13        }
14      
15        // Initialize a counter for the number of cells with odd values
16        int oddValueCount = 0;
17      
18        // Iterate over each cell to determine if the sum of increments
19        // for the corresponding row and column is odd
20        for (int i = 0; i < m; i++) {
21            for (int j = 0; j < n; j++) {
22                if ((rowCount[i] + colCount[j]) % 2 != 0) {
23                    // Increment the count if the cell value is odd
24                    oddValueCount++;
25                }
26            }
27        }
28      
29        // Return the total count of cells with odd values
30        return oddValueCount;
31    }
32}
33

C++ Solution

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    // Function to count how many cells will have odd values after performing the operations indicated in 'indices'
7    int oddCells(int numberOfRows, int numberOfColumns, vector<vector<int>>& indices) {
8        vector<int> rows(numberOfRows, 0); // Create a vector to keep track of increments in each row
9        vector<int> cols(numberOfColumns, 0); // Create a vector to keep track of increments in each column
10      
11        // Iterate over each pair of indices and increment the relevant rows and columns
12        for (const vector<int>& indexPair : indices) {
13            int rowIndex = indexPair[0];
14            int colIndex = indexPair[1];
15            rows[rowIndex]++;
16            cols[colIndex]++;
17        }
18      
19        int oddCount = 0; // Initialize a counter for cells with odd values
20      
21        // Nested loop to count the cells that will have odd values
22        for (int i = 0; i < numberOfRows; ++i) {
23            for (int j = 0; j < numberOfColumns; ++j) {
24                // If the sum of the increments for the current cell's row and column is odd, increment oddCount
25                if ((rows[i] + cols[j]) % 2 != 0) {
26                    oddCount++;
27                }
28            }
29        }
30      
31        // Return the total count of cells with odd values
32        return oddCount;
33    }
34};
35

Typescript Solution

1// Importing the 'Array' type from TypeScript for type definitions
2import { Array } from "typescript";
3
4// Function to count how many cells will have odd values after performing the operations indicated in 'indices'
5function oddCells(numberOfRows: number, numberOfColumns: number, indices: Array<Array<number>>): number {
6    // Create an array to keep track of increments in each row
7    let rows: Array<number> = new Array(numberOfRows).fill(0);
8    // Create an array to keep track of increments in each column
9    let cols: Array<number> = new Array(numberOfColumns).fill(0);
10  
11    // Iterate over each pair of indices and increment the respective rows and columns
12    indices.forEach(indexPair => {
13        let rowIndex: number = indexPair[0];
14        let colIndex: number = indexPair[1];
15        rows[rowIndex]++;
16        cols[colIndex]++;
17    });
18  
19    // Initialize a counter for cells with odd values
20    let oddCount: number = 0;
21  
22    // Nested loop to count the cells that will have odd values
23    for (let i = 0; i < numberOfRows; i++) {
24        for (let j = 0; j < numberOfColumns; j++) {
25            // If the sum of the increments for the current cell's row and column is odd, increment oddCount
26            if ((rows[i] + cols[j]) % 2 !== 0) {
27                oddCount++;
28            }
29        }
30    }
31  
32    // Return the total count of cells with odd values
33    return oddCount;
34}
35

Time and Space Complexity

The time complexity of the provided code is O(m * n + k), where m is the number of rows, n is the number of columns, and k is the length of the indices list. This is because the code consists of a single loop through the indices list, which takes O(k) time, followed by a nested loop that iterates through all possible combinations of rows and columns, taking O(m * n) time. The addition of these two gives the final time complexity.

The space complexity of the code is O(m + n), as it requires additional space to store the row and col arrays, whose sizes are proportional to the number of rows m and columns n, respectively.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫