Question

2768. Number of Black Blocks

中文文档

Description

You are given two integers m and n representing the dimensions of a 0-indexed m x n grid.

You are also given a 0-indexed 2D integer matrix coordinates, where coordinates[i] = [x, y] indicates that the cell with coordinates [x, y] is colored black. All cells in the grid that do not appear in coordinates are white.

A block is defined as a 2 x 2 submatrix of the grid. More formally, a block with cell [x, y] as its top-left corner where 0 <= x < m - 1 and 0 <= y < n - 1 contains the coordinates [x, y], [x + 1, y], [x, y + 1], and [x + 1, y + 1].

Return _a 0-indexed integer array_ arr _of size_ 5 _such that_ arr[i] _is the number of blocks that contains exactly_ i _black cells_.

 

Example 1:

Input: m = 3, n = 3, coordinates = [[0,0]]
Output: [3,1,0,0,0]
Explanation: The grid looks like this:

There is only 1 block with one black cell, and it is the block starting with cell [0,0].
The other 3 blocks start with cells [0,1], [1,0] and [1,1]. They all have zero black cells. 
Thus, we return [3,1,0,0,0]. 

Example 2:

Input: m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
Output: [0,2,2,0,0]
Explanation: The grid looks like this:

There are 2 blocks with two black cells (the ones starting with cell coordinates [0,0] and [0,1]).
The other 2 blocks have starting cell coordinates of [1,0] and [1,1]. They both have 1 black cell.
Therefore, we return [0,2,2,0,0].

 

Constraints:

• 2 <= m <= 105
• 2 <= n <= 105
• 0 <= coordinates.length <= 104
• coordinates[i].length == 2
• 0 <= coordinates[i][0] < m
• 0 <= coordinates[i][1] < n
• It is guaranteed that coordinates contains pairwise distinct coordinates.

Solutions

Solution 1: Hash Table

For each $2 \times 2$ submatrix, we can use its upper-left corner coordinate $(x, y)$ to represent it.

For each black cell $(x, y)$, its contribution to the 4 submatrices is $1$, namely the matrices $(x - 1, y - 1)$, $(x - 1, y)$, $(x, y - 1)$, $(x, y)$.

Therefore, we traverse all the black cells, and then accumulate the number of black cells in each submatrix, recorded in the hash table $cnt$.

Finally, we traverse all the values in $cnt$ (greater than $0$), count the number of times they appear, and record them in the answer array $ans$, while $ans[0]$ represents the number of submatrices without black cells, the value is $(m - 1) \times (n - 1) - \sum_{i = 1}^4 ans[i]$.

Time complexity $O(l)$, space complexity $O(l)$, where $l$ is the length of $coordinates$.

class Solution:
  def countBlackBlocks(
    self, m: int, n: int, coordinates: List[List[int]]
  ) -> List[int]:
    cnt = Counter()
    for x, y in coordinates:
      for a, b in pairwise((0, 0, -1, -1, 0)):
        i, j = x + a, y + b
        if 0 <= i < m - 1 and 0 <= j < n - 1:
          cnt[(i, j)] += 1
    ans = [0] * 5
    for x in cnt.values():
      ans[x] += 1
    ans[0] = (m - 1) * (n - 1) - len(cnt.values())
    return ans

class Solution {
  public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
    Map<Long, Integer> cnt = new HashMap<>(coordinates.length);
    int[] dirs = {0, 0, -1, -1, 0};
    for (var e : coordinates) {
      int x = e[0], y = e[1];
      for (int k = 0; k < 4; ++k) {
        int i = x + dirs[k], j = y + dirs[k + 1];
        if (i >= 0 && i < m - 1 && j >= 0 && j < n - 1) {
          cnt.merge(1L * i * n + j, 1, Integer::sum);
        }
      }
    }
    long[] ans = new long[5];
    ans[0] = (m - 1L) * (n - 1);
    for (int x : cnt.values()) {
      ++ans[x];
      --ans[0];
    }
    return ans;
  }
}

class Solution {
public:
  vector<long long> countBlackBlocks(int m, int n, vector<vector<int>>& coordinates) {
    unordered_map<long long, int> cnt;
    int dirs[5] = {0, 0, -1, -1, 0};
    for (auto& e : coordinates) {
      int x = e[0], y = e[1];
      for (int k = 0; k < 4; ++k) {
        int i = x + dirs[k], j = y + dirs[k + 1];
        if (i >= 0 && i < m - 1 && j >= 0 && j < n - 1) {
          ++cnt[1LL * i * n + j];
        }
      }
    }
    vector<long long> ans(5);
    ans[0] = (m - 1LL) * (n - 1);
    for (auto& [_, x] : cnt) {
      ++ans[x];
      --ans[0];
    }
    return ans;
  }
};

func countBlackBlocks(m int, n int, coordinates [][]int) []int64 {
  cnt := map[int64]int{}
  dirs := [5]int{0, 0, -1, -1, 0}
  for _, e := range coordinates {
    x, y := e[0], e[1]
    for k := 0; k < 4; k++ {
      i, j := x+dirs[k], y+dirs[k+1]
      if i >= 0 && i < m-1 && j >= 0 && j < n-1 {
        cnt[int64(i*n+j)]++
      }
    }
  }
  ans := make([]int64, 5)
  ans[0] = int64((m - 1) * (n - 1))
  for _, x := range cnt {
    ans[x]++
    ans[0]--
  }
  return ans
}

function countBlackBlocks(m: number, n: number, coordinates: number[][]): number[] {
  const cnt: Map<number, number> = new Map();
  const dirs: number[] = [0, 0, -1, -1, 0];
  for (const [x, y] of coordinates) {
    for (let k = 0; k < 4; ++k) {
      const [i, j] = [x + dirs[k], y + dirs[k + 1]];
      if (i >= 0 && i < m - 1 && j >= 0 && j < n - 1) {
        const key = i * n + j;
        cnt.set(key, (cnt.get(key) || 0) + 1);
      }
    }
  }
  const ans: number[] = Array(5).fill(0);
  ans[0] = (m - 1) * (n - 1);
  for (const [_, x] of cnt) {
    ++ans[x];
    --ans[0];
  }
  return ans;
}