Skip to content

2768. Number of Black Blocks 👍

  • Time: $O(|\texttt{coordinates}|)$
  • Space: $O(|\texttt{coordinates}|)$
 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
class Solution {
 public:
  vector<long long> countBlackBlocks(int m, int n,
                                     vector<vector<int>>& coordinates) {
    vector<long long> ans(5);
    // count[i * n + j] := the number of black cells in
    // (i - 1, j - 1), (i - 1, j), (i, j - 1), (i, j)
    unordered_map<long, int> count;

    for (const vector<int>& coordinate : coordinates) {
      const int x = coordinate[0];
      const int y = coordinate[1];
      for (long i = x; i < x + 2; ++i)
        for (long j = y; j < y + 2; ++j)
          // 2 x 2 submatrix with right-bottom conner being (i, j) contains the
          // current black cell (x, y).
          if (i - 1 >= 0 && i < m && j - 1 >= 0 && j < n)
            ++count[i * n + j];
    }

    for (const auto& [_, freq] : count)
      ++ans[freq];

    ans[0] = (m - 1L) * (n - 1) - accumulate(ans.begin(), ans.end(), 0L);
    return ans;
  }
};

 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
class Solution {
  public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
    long[] ans = new long[5];
    // count[i * n + j] := the number of black cells in
    // (i - 1, j - 1), (i - 1, j), (i, j - 1), (i, j)
    Map<Long, Integer> count = new HashMap<>();

    for (int[] coordinate : coordinates) {
      final int x = coordinate[0];
      final int y = coordinate[1];
      for (long i = x; i < x + 2; ++i)
        for (long j = y; j < y + 2; ++j)
          // 2 x 2 submatrix with right-bottom conner being (i, j) contains the
          // current black cell (x, y).
          if (i - 1 >= 0 && i < m && j - 1 >= 0 && j < n)
            count.merge(i * n + j, 1, Integer::sum);
    }

    for (final int freq : count.values())
      ++ans[freq];

    ans[0] = (m - 1L) * (n - 1) - Arrays.stream(ans).sum();
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:
    ans = [0] * 5
    # count[i * n + j] := the number of black cells in
    # (i - 1, j - 1), (i - 1, j), (i, j - 1), (i, j)
    count = collections.Counter()

    for x, y in coordinates:
      for i in range(x, x + 2):
        for j in range(y, y + 2):
          # 2 x 2 submatrix with right-bottom conner being (i, j) contains the
          # current black cell (x, y).
          if 0 < i < m and 0 < j < n:
            count[(i, j)] += 1

    for freq in count.values():
      ans[freq] += 1

    ans[0] = (m - 1) * (n - 1) - sum(ans)
    return ans