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 <= 1052 <= n <= 1050 <= coordinates.length <= 104coordinates[i].length == 20 <= coordinates[i][0] < m0 <= 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$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 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
|
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 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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;
}
|
