Cells with Odd Values in a Matrix

Easy
301.

Cells with Odd Values in a Matrix

Cells with Odd Values in a Matrix is an easy coding problem on arrays, math and simulation, asked in Amazon and Adobe interviews.

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 <= 8
  • 1 <= indices.length <= 20
  • indices[i] is a valid [row, column] pair.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} indices
 * @return {number}
 */
var oddCells = function(m, n, indices) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 8
  • 1 <= indices.length <= 20
  • indices[i] is a valid [row, column] pair.

Hints for Cells with Odd Values in a Matrix

  1. Hint 1

    Simulating the whole matrix works, but you only ever need per-row and per-column tallies.

  2. Hint 2

    Cell (r, c) ends at rowCount[r] + colCount[c].

  3. 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

  1. Tally how many times each row and each column is incremented.
  2. 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