Cells with Odd Values in a Matrix (LeetCode 1252): Count Rows and Columns, Not Cells

The problem: start with an m x n matrix of zeros. Each entry [r, c] in indices adds 1 to every cell in row r and every cell in column c. Return how many cells end up odd.

Brute force

Build the matrix and apply every increment: O(k * (m + n)) for the updates plus O(m * n) to count. Fine for the small limits, but the interviewer is waiting for the better idea.

Parity per row and column

The value at (i, j) is row[i] + col[j], where row[i] counts how often row i was incremented. It is odd exactly when one of the two is odd and the other even.

def oddCells(m, n, indices):
    row = [0] * m
    col = [0] * n
    for r, c in indices:
        row[r] ^= 1
        col[c] ^= 1
    odd_r = sum(row)
    odd_c = sum(col)
    return odd_r * (n - odd_c) + (m - odd_r) * odd_c

Only parity matters, so XOR with 1 is enough. If odd_r rows are odd and odd_c columns are odd, odd cells come from an odd row with an even column, or an even row with an odd column. Time O(k + m + n), space O(m + n).

How to present it

  1. Write the brute force in one sentence and give its cost.
  2. Observe that a cell's value is a sum of two independent counters.
  3. Reduce to parity, then count combinations.

That reasoning step, turning a 2D grid into two 1D arrays, is the reusable lesson. It shows up again in Range Addition II and in problems that toggle whole rows or columns of a binary matrix.

Quick check

m = 2, n = 3, indices = [[0,1],[1,1]]. Rows 0 and 1 are each incremented once, so row parity is [1,1]. Column 1 is incremented twice, so column parity is [0,0,0]. That gives odd_r = 2 and odd_c = 0, so the answer is 2 * 3 + 0 * 0 = 6. By hand the final matrix is [[1,3,1],[1,3,1]], and all 6 cells are odd, which matches.


I help build best AI tool for coding tests and OAs at Linkjob AI. (Disclosure: affiliated.)

Further reading: Linkjob AI resource directory

评论

此博客中的热门博文

Task Scheduler in a Coding Interview: The Idle-Slot Formula Explained

How to Answer "What Motivates You?" in a Job Interview