1252. Cells with Odd Values in a Matrix
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 0
Acceptance rate: 78.7%
Problem Breakdown
The problem requires us to determine the number of odd-valued cells in an m x n matrix after performing a series of increment operations specified by the indices array. The matrix starts with all elements initialized to 0. For each index [ri, ci] in indices, we increment all elements in row ri and column ci. The task is to return the count of cells that have odd values after all increments.
Inputs:
m: Number of rows in the matrix.n: Number of columns in the matrix.indices: A 2D array where each element[ri, ci]indicates a row and column index to increment.
Outputs:
- An integer representing the number of cells with odd values after all increments.
Implicit Constraints/Edge Cases:
- The matrix size can be as large as 50x50.
- The
indicesarray can have up to 100 elements. - Indices are guaranteed to be within bounds.
Intuition
A brute-force approach would involve creating the matrix and directly incrementing the specified rows and columns for each index in indices. This approach has a time complexity of O(m * n * indices.length), which is inefficient given the constraints.
The key insight is that we don’t need to explicitly construct the matrix. Instead, we can track the number of increments for each row and column using two separate arrays. By doing this, we can determine if a cell’s value will be odd or even based on the parity (odd/even nature) of the sum of its corresponding row and column increment counts.
Approach
- Initialize two arrays,
row_incrementsof sizemandcol_incrementsof sizen, to zero. - For each index
[ri, ci]inindices, incrementrow_increments[ri]andcol_increments[ci]. - Initialize a counter for odd-valued cells.
- Iterate through each cell
(i, j)in the matrix:- Calculate the total number of increments for this cell as
row_increments[i] + col_increments[j]. - If this sum is odd, increment the odd-valued cell counter.
- Calculate the total number of increments for this cell as
- Return the counter.
This approach leverages the fact that a cell’s value will be odd if and only if the sum of its row and column increments is odd. This reduces the time complexity to O(m + n + indices.length) and space complexity to O(m + n).
Complexity Analysis
-
Time Complexity: O(m + n + indices.length)
- We iterate through
indicesonce, which takes O(indices.length). - We then iterate through each cell in the matrix, but since we only need to check the parity of the sum of row and column increments, this is effectively O(m + n).
- We iterate through
-
Space Complexity: O(m + n)
- We use two arrays,
row_incrementsandcol_increments, each of sizemandnrespectively.
- We use two arrays,
Solution
def oddCells(m: int, n: int, indices: List[List[int]]) -> int:
row_increments = [0] * m
col_increments = [0] * n
for ri, ci in indices:
row_increments[ri] += 1
col_increments[ci] += 1
odd_count = 0
for i in range(m):
for j in range(n):
if (row_increments[i] + col_increments[j]) % 2 == 1:
odd_count += 1
return odd_count
Edge Cases Handled
- Empty
indices: Ifindicesis empty, the matrix remains unchanged with all zeros, so the function returns 0. - All indices pointing to the same row or column: The increments for that row or column will be higher, but the logic correctly tracks the parity of the sum.
- Maximum constraints (
m = n = 50,indices.length = 100): The solution efficiently handles these maximum values within the given time and space limits.