Skip to content

1252. Cells with Odd Values in a Matrix 👎

Approach 1: Traverse all cells

  • Time: $O(mn + |\texttt{indices}|)$
  • Space: $O(m + n)$
 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, vector<vector<int>>& indices) {
    int ans = 0;
    // rows[i] and cols[i] :=
    //   true (flipped even times) / false (flipped odd times)
    vector<bool> rows(m);
    vector<bool> cols(n);

    for (const vector<int>& index : indices) {
      rows[index[0]] = rows[index[0]] ^ true;
      cols[index[1]] = cols[index[1]] ^ true;
    }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        ans += rows[i] ^ cols[j];

    return ans;
  }
};

 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 ans = 0;
    // rows[i] and cols[i] :=
    //   true (flipped even times) / false (flipped odd times)
    boolean[] rows = new boolean[n];
    boolean[] cols = new boolean[n];

    for (int[] index : indices) {
      rows[index[0]] = rows[index[0]] ^ true;
      cols[index[1]] = cols[index[1]] ^ true;
    }

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        if (rows[i] ^ cols[j])
          ++ans;

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
    # rows[i] and cols[i] :=
    #   true (flipped even times) / false (flipped odd times)
    rows = [False] * m
    cols = [False] * n

    for r, c in indices:
      rows[r] ^= True
      cols[c] ^= True

    return sum(rows[i] ^ cols[j]
               for i in range(m)
               for j in range(n))

Approach 2: Math

  • Time: $O(m + n + |\texttt{indices}|)$
  • Space: $O(m + n)$
 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) {
    // rows[i] and cols[i] :=
    //   true (flipped even times) / false (flipped odd times)
    vector<bool> rows(m);
    vector<bool> cols(n);

    for (const vector<int>& index : indices) {
      rows[index[0]] = rows[index[0]] ^ true;
      cols[index[1]] = cols[index[1]] ^ true;
    }

    const int oddRowsCount = count(begin(rows), end(rows), true);
    const int oddColsCount = count(begin(cols), end(cols), true);
    const int evenRowsCount = m - oddRowsCount;
    const int evenColsCount = n - oddColsCount;
    return oddRowsCount * evenColsCount + oddColsCount * evenRowsCount;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public int oddCells(int m, int n, int[][] indices) {
    // rows[i] and cols[i] :=
    //   true (flipped even times) / false (flipped odd times)
    boolean[] rows = new boolean[n];
    boolean[] cols = new boolean[n];

    for (int[] index : indices) {
      rows[index[0]] = rows[index[0]] ^ true;
      cols[index[1]] = cols[index[1]] ^ true;
    }

    int oddRowsCount = 0;
    int oddColsCount = 0;

    for (boolean row : rows)
      if (row)
        ++oddRowsCount;

    for (boolean col : cols)
      if (col)
        ++oddColsCount;

    final int evenRowsCount = m - oddRowsCount;
    final int evenColsCount = n - oddColsCount;
    return oddRowsCount * evenColsCount + oddColsCount * evenRowsCount;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
    # rows[i] and cols[i] :=
    #   True (flipped even times) // False (flipped odd times)
    rows = [False] * m
    cols = [False] * n

    for r, c in indices:
      rows[r] ^= True
      cols[c] ^= True

    oddRowsCount = rows.count(True)
    oddColsCount = cols.count(True)
    evenRowsCount = m - oddRowsCount
    evenColsCount = n - oddColsCount
    return oddRowsCount * evenColsCount + oddColsCount * evenRowsCount

Approach 3: Math (Set)

  • Time: $O(|\texttt{indices}|)$
  • Space: $O(|\texttt{indices}|)$
 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) {
    unordered_set<int> oddRows;
    unordered_set<int> oddCols;

    for (const vector<int>& index : indices) {
      const int r = index[0];
      const int c = index[1];
      if (!oddRows.insert(r).second)
        oddRows.erase(r);
      if (!oddCols.insert(c).second)
        oddCols.erase(c);
    }

    return oddRows.size() * (n - oddCols.size()) +
           oddCols.size() * (m - oddRows.size());
  }
};