Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1252. Cells with Odd Values in a Matrix - Leetcode Solution

Code Implementation

class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        rows = [0] * m
        cols = [0] * n
        for r, c in indices:
            rows[r] += 1
            cols[c] += 1
        count = 0
        for i in range(m):
            for j in range(n):
                if (rows[i] + cols[j]) % 2 == 1:
                    count += 1
        return count
    
class Solution {
public:
    int oddCells(int m, int n, vector<vector<int>>& indices) {
        vector<int> rows(m, 0), cols(n, 0);
        for (const auto& idx : indices) {
            rows[idx[0]]++;
            cols[idx[1]]++;
        }
        int count = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((rows[i] + cols[j]) % 2 == 1)
                    count++;
            }
        }
        return count;
    }
};
    
class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[] rows = new int[m];
        int[] cols = new int[n];
        for (int[] idx : indices) {
            rows[idx[0]]++;
            cols[idx[1]]++;
        }
        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((rows[i] + cols[j]) % 2 == 1)
                    count++;
            }
        }
        return count;
    }
}
    
var oddCells = function(m, n, indices) {
    let rows = new Array(m).fill(0);
    let cols = new Array(n).fill(0);
    for (let [r, c] of indices) {
        rows[r]++;
        cols[c]++;
    }
    let count = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if ((rows[i] + cols[j]) % 2 === 1)
                count++;
        }
    }
    return count;
};

Problem Description

You are given an m x n matrix initialized with all 0s. You are also given a list of indices, where each element is a pair [ri, ci] representing a row index and a column index. For each pair [ri, ci], every cell in row ri and column ci is incremented by 1. After performing all operations, your task is to return the number of cells in the matrix that have an odd value.
  • Each operation affects an entire row and an entire column.
  • You must not reuse elements or rows/columns unless specified by the input.
  • There is always one valid solution.
  • The input indices can have repeated rows or columns.

Thought Process

At first glance, you might think you need to simulate every operation directly on the matrix. This would mean looping through each pair in indices and incrementing all elements in the corresponding row and column. However, this approach can be inefficient, especially for large matrices. Instead, let's consider what actually determines the final value of each cell:
  • Each cell at position (i, j) is incremented every time its row i or its column j is targeted.
  • So, the value at (i, j) after all operations is row_increments[i] + col_increments[j].
  • We only care about whether this sum is odd or even.
This realization lets us avoid updating the entire matrix and focus on just counting row and column increments.

Solution Approach

Let's break down the optimized solution step by step:
  1. Track Row and Column Increments:
    • Create two arrays: rows of size m and cols of size n.
    • For each pair [ri, ci] in indices, increment rows[ri] and cols[ci] by 1.
  2. Count Odd Cells:
    • For each cell (i, j), its final value is rows[i] + cols[j].
    • If this sum is odd, increment a counter.
  3. Return the Result:
    • After checking all cells, return the counter as the answer.

This approach is efficient because it avoids modifying the entire matrix and only needs two passes: one to process indices and one to count odd cells.

Example Walkthrough

Let's use a sample input to see how the solution works step by step:
  • Input: m = 2, n = 3, indices = [[0,1],[1,1]]
  • Initialize rows = [0, 0] and cols = [0, 0, 0].
  • Process [0,1]: rows = [1, 0], cols = [0, 1, 0]
  • Process [1,1]: rows = [1, 1], cols = [0, 2, 0]
  • Now, for each cell, compute rows[i] + cols[j]:
    • (0,0): 1+0=1 (odd)
    • (0,1): 1+2=3 (odd)
    • (0,2): 1+0=1 (odd)
    • (1,0): 1+0=1 (odd)
    • (1,1): 1+2=3 (odd)
    • (1,2): 1+0=1 (odd)
  • All 6 cells are odd, so the answer is 6.

Time and Space Complexity

  • Brute-force Approach:
    • For each index, increment all cells in a row and column. This takes O(k*(m+n)), where k is the number of indices.
    • Total space: O(mn) for the matrix.
  • Optimized Approach:
    • Processing indices: O(k).
    • Counting odd cells: O(mn).
    • Total time: O(k + mn).
    • Space: O(m + n) for the row and column arrays.
  • This is much more efficient, especially for large matrices and small numbers of operations.

Summary

The key insight is that you only need to know how many times each row and column is incremented, not the actual values of every cell. By tracking row and column increments separately and then combining them to determine odd cells, the solution is both elegant and efficient. This avoids unnecessary computation and demonstrates the power of reducing a problem to its essential operations.