Cells with Odd Values in a Matrix
Easy · Matrix · Array · Math · Simulation
Problem
Start with an m x n matrix filled with zeros. You are given a list indices where each entry [r, c] describes one operation: add 1 to every cell in row r, then add 1 to every cell in column c. (The cell where they cross is therefore increased twice.)
After applying all operations in order, return the number of cells that hold an odd value.
Examples
Input: m = 2, n = 3, indices = [[0,2]] Output: 3
Row 0 becomes [1,1,1] and column 2 then adds 1 down the column, giving [[1,1,2],[0,0,1]]: three odd cells.
Input: m = 3, n = 3, indices = [[0,0],[1,1]] Output: 4
Rows 0 and 1 and columns 0 and 1 are each picked once. A cell is odd when exactly one of its row and column was picked: (0,2), (1,2), (2,0) and (2,1).
Input: m = 2, n = 2, indices = [[0,0],[0,0]] Output: 0
Row 0 and column 0 are each picked twice, so every cell is even.
Constraints
- 1 <= m, n <= 50
- 1 <= len(indices) <= 100
- 0 <= r < m
- 0 <= c < n
Approaches
- Baseline: build the grid and replay — time O(L · (m + n) + m · n), space O(m · n)
Follow-up
With up to 10^5 rows, columns and operations, the grid would be too big to build, but the parity counts still take O(m + n + L) time and O(m + n) space. Could you do it with only two counters and two bit sets?
Related problems
Start free on Cariara · Coding problems · System design studio
