Skip to content

1252. Cells with Odd Values in a Matrix

Description

There is an m x n matrix that is initialized to all 0's. There is also a 2D array indices where each indices[i] = [ri, ci] represents a 0-indexed location to perform some increment operations on the matrix.

For each location indices[i], do both of the following:

  1. Increment all the cells on row ri.
  2. Increment all the cells on column ci.

Given m, n, and indices, return the number of odd-valued cells in the matrix after applying the increment to all locations in indices.

 

Example 1:

Input: m = 2, n = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Initial matrix = [[0,0,0],[0,0,0]].
After applying first increment it becomes [[1,2,1],[0,1,0]].
The final matrix is [[1,3,1],[1,3,1]], which contains 6 odd numbers.

Example 2:

Input: m = 2, n = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]]. There are no odd numbers in the final matrix.

 

Constraints:

  • 1 <= m, n <= 50
  • 1 <= indices.length <= 100
  • 0 <= ri < m
  • 0 <= ci < n

 

Follow up: Could you solve this in O(n + m + indices.length) time with only O(n + m) extra space?

Solutions

Solution 1: Simulation

Thinking

With \(m,n \le 50\) we may allocate the matrix, add one to a whole row and column per operation, then count odds. The simulation follows the statement and is the baseline for later optimizations.

We create a matrix \(g\) to store the result of operations. For each pair \((r_i, c_i)\) in \(\textit{indices}\), we add \(1\) to all numbers in the \(r_i\)-th row of the matrix and add \(1\) to all elements in the \(c_i\)-th column.

After the simulation ends, we traverse the matrix and count the number of odd numbers.

The time complexity is \(O(k \times (m + n) + m \times n)\), and the space complexity is \(O(m \times n)\). Here, \(k\) is the length of \(\textit{indices}\).

1
2
3
4
5
6
7
8
9
class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        g = [[0] * n for _ in range(m)]
        for r, c in indices:
            for i in range(m):
                g[i][c] += 1
            for j in range(n):
                g[r][j] += 1
        return sum(v % 2 for row in g for v in row)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[][] g = new int[m][n];
        for (int[] e : indices) {
            int r = e[0], c = e[1];
            for (int i = 0; i < m; ++i) {
                g[i][c]++;
            }
            for (int j = 0; j < n; ++j) {
                g[r][j]++;
            }
        }
        int ans = 0;
        for (int[] row : g) {
            for (int v : row) {
                ans += v % 2;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int oddCells(int m, int n, vector<vector<int>>& indices) {
        vector<vector<int>> g(m, vector<int>(n));
        for (auto& e : indices) {
            int r = e[0], c = e[1];
            for (int i = 0; i < m; ++i) {
                ++g[i][c];
            }
            for (int j = 0; j < n; ++j) {
                ++g[r][j];
            }
        }
        int ans = 0;
        for (auto& row : g) {
            for (int v : row) {
                ans += v % 2;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func oddCells(m int, n int, indices [][]int) int {
    g := make([][]int, m)
    for i := range g {
        g[i] = make([]int, n)
    }
    for _, e := range indices {
        r, c := e[0], e[1]
        for i := 0; i < m; i++ {
            g[i][c]++
        }
        for j := 0; j < n; j++ {
            g[r][j]++
        }
    }
    ans := 0
    for _, row := range g {
        for _, v := range row {
            ans += v % 2
        }
    }
    return ans
}

Solution 2: Space Optimization

Thinking

Solution 1 writes \(O(m+n)\) cells per operation and stores the full matrix. Cell \((i,j)\) ends at (row-\(i\) hits) plus (column-\(j\) hits). Two arrays store those increments; we then test each cell's parity. Extra space is \(O(m+n)\).

We can use a row array \(\textit{row}\) and a column array \(\textit{col}\) to record the number of times each row and column is incremented. For each pair \((r_i, c_i)\) in \(\textit{indices}\), we add \(1\) to \(\textit{row}[r_i]\) and \(\textit{col}[c_i]\) respectively.

After the operations are completed, the count at position \((i, j)\) can be calculated as \(\textit{row}[i] + \textit{col}[j]\). We traverse the matrix and count the number of odd numbers.

The time complexity is \(O(k + m \times n)\), and the space complexity is \(O(m + n)\). Here, \(k\) is the length of \(\textit{indices}\).

1
2
3
4
5
6
7
8
class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        row = [0] * m
        col = [0] * n
        for r, c in indices:
            row[r] += 1
            col[c] += 1
        return sum((i + j) % 2 for i in row for j in col)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[] row = new int[m];
        int[] col = new int[n];
        for (int[] e : indices) {
            int r = e[0], c = e[1];
            row[r]++;
            col[c]++;
        }
        int ans = 0;
        for (int i : row) {
            for (int j : col) {
                ans += (i + j) % 2;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int oddCells(int m, int n, vector<vector<int>>& indices) {
        vector<int> row(m);
        vector<int> col(n);
        for (auto& e : indices) {
            int r = e[0], c = e[1];
            row[r]++;
            col[c]++;
        }
        int ans = 0;
        for (int i : row) {
            for (int j : col) {
                ans += (i + j) % 2;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func oddCells(m int, n int, indices [][]int) int {
    row := make([]int, m)
    col := make([]int, n)
    for _, e := range indices {
        r, c := e[0], e[1]
        row[r]++
        col[c]++
    }
    ans := 0
    for _, i := range row {
        for _, j := range col {
            ans += (i + j) % 2
        }
    }
    return ans
}

Solution 3: Mathematical Optimization

Thinking

Solution 2 still visits every cell. \((i,j)\) is odd iff the row and column increments have opposite parity. With \(cnt1\) odd rows and \(cnt2\) odd columns, the odd count is \(cnt1(n-cnt2)+cnt2(m-cnt1)\), in \(O(k+m+n)\) time.

We notice that a number at position \((i, j)\) in the matrix will be odd only when exactly one of \(\textit{row}[i]\) and \(\textit{col}[j]\) is odd and the other is even.

We count the number of odd numbers in \(\textit{row}\), denoted as \(\textit{cnt1}\), and the number of odd numbers in \(\textit{col}\), denoted as \(\textit{cnt2}\). Therefore, the final count of odd numbers is \(\textit{cnt1} \times (n - \textit{cnt2}) + \textit{cnt2} \times (m - \textit{cnt1})\).

The time complexity is \(O(k + m + n)\), and the space complexity is \(O(m + n)\). Here, \(k\) is the length of \(\textit{indices}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
        row = [0] * m
        col = [0] * n
        for r, c in indices:
            row[r] += 1
            col[c] += 1
        cnt1 = sum(v % 2 for v in row)
        cnt2 = sum(v % 2 for v in col)
        return cnt1 * (n - cnt2) + cnt2 * (m - cnt1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int oddCells(int m, int n, int[][] indices) {
        int[] row = new int[m];
        int[] col = new int[n];
        for (int[] e : indices) {
            int r = e[0], c = e[1];
            row[r]++;
            col[c]++;
        }
        int cnt1 = 0, cnt2 = 0;
        for (int v : row) {
            cnt1 += v % 2;
        }
        for (int v : col) {
            cnt2 += v % 2;
        }
        return cnt1 * (n - cnt2) + cnt2 * (m - cnt1);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int oddCells(int m, int n, vector<vector<int>>& indices) {
        vector<int> row(m);
        vector<int> col(n);
        for (auto& e : indices) {
            int r = e[0], c = e[1];
            row[r]++;
            col[c]++;
        }
        int cnt1 = 0, cnt2 = 0;
        for (int v : row) {
            cnt1 += v % 2;
        }
        for (int v : col) {
            cnt2 += v % 2;
        }
        return cnt1 * (n - cnt2) + cnt2 * (m - cnt1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func oddCells(m int, n int, indices [][]int) int {
    row := make([]int, m)
    col := make([]int, n)
    for _, e := range indices {
        r, c := e[0], e[1]
        row[r]++
        col[c]++
    }
    cnt1, cnt2 := 0, 0
    for _, v := range row {
        cnt1 += v % 2
    }
    for _, v := range col {
        cnt2 += v % 2
    }
    return cnt1*(n-cnt2) + cnt2*(m-cnt1)
}

Comments