Domain 1EasyCORE

Cells with Odd Values in a Matrix

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 0

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 indices array 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

  1. Initialize two arrays, row_increments of size m and col_increments of size n, to zero.
  2. For each index [ri, ci] in indices, increment row_increments[ri] and col_increments[ci].
  3. Initialize a counter for odd-valued cells.
  4. 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.
  5. 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 indices once, 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).
  • Space Complexity: O(m + n)

    • We use two arrays, row_increments and col_increments, each of size m and n respectively.

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: If indices is 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.