Cells with Odd Values in a Matrix — Problem & Solution
Cells with Odd Values in a Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Cells with Odd Values in a Matrix is an easy coding problem on arrays, math and simulation, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Math, Simulation
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
There is an m × n matrix that starts out all zeros. You are given indices, where each indices[i] = [r, c] means: increment every cell of row r and every cell of column c by one.
Return the number of cells holding an odd value after all the operations.
Example 1
Input: m = 2, n = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Every cell ends up odd.
Example 2
Input: m = 2, n = 2, indices = [[1,1],[0,0]]
Output: 0
Example 3
Input: m = 1, n = 1, indices = [[0,0]]
Output: 0
Explanation: The single cell is incremented twice.
Constraints
1 <= m, n <= 81 <= indices.length <= 20indices[i] is a valid [row, column] pair.
Hints for Cells with Odd Values in a Matrix
Hint 1
Simulating the whole matrix works, but you only ever need per-row and per-column tallies.
Hint 2
Cell
(r, c)ends atrowCount[r] + colCount[c].Hint 3
Its parity is odd exactly when those two counts have different parities.
How to solve Cells with Odd Values in a Matrix
Cell (r, c) ends at rowCount[r] + colCount[c], which is odd exactly when the two counts have different parity.
Approach
- Tally how many times each row and each column is incremented.
- Count cells where
(rowCount[r] + colCount[c]) % 2 == 1.
Why it works
Each operation adds one to an entire row and an entire column, so the final value of a cell is the sum of its row's and column's operation counts.
Complexity
- Time —
O(m · n + |indices|) - Space —
O(m + n)
Pitfalls
- Counting odd rows and odd columns gives O(m + n):
oddRows·(n - oddCols) + oddCols·(m - oddRows).
Reference solution
Python
def oddCells(m: int, n: int, indices) -> int:
row_count = [0] * m
col_count = [0] * n
for r, c in indices:
row_count[r] += 1
col_count[c] += 1
return sum(1 for r in range(m) for c in range(n)
if (row_count[r] + col_count[c]) % 2 == 1)Java
public static int oddCells(int m, int n, int[][] indices) {
int[] rowCount = new int[m];
int[] colCount = new int[n];
for (int[] idx : indices) {
rowCount[idx[0]]++;
colCount[idx[1]]++;
}
int odd = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if ((rowCount[r] + colCount[c]) % 2 == 1) odd++;
}
}
return odd;
}C++
int oddCells(int m, int n, vector<vector<int>>& indices) {
vector<int> rowCount(m, 0), colCount(n, 0);
for (vector<int>& idx : indices) {
rowCount[idx[0]]++;
colCount[idx[1]]++;
}
int odd = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if ((rowCount[r] + colCount[c]) % 2 == 1) odd++;
}
}
return odd;
}JavaScript
var oddCells = function(m, n, indices) {
const rowCount = new Array(m).fill(0);
const colCount = new Array(n).fill(0);
for (let i = 0; i < indices.length; i++) {
rowCount[indices[i][0]]++;
colCount[indices[i][1]]++;
}
let odd = 0;
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if ((rowCount[r] + colCount[c]) % 2 === 1) odd++;
}
}
return odd;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays