comments | difficulty | edit_url | rating | source | tags | |||
---|---|---|---|---|---|---|---|---|
true |
Medium |
2175 |
Biweekly Contest 108 Q4 |
|
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.
For each
For each black cell
Therefore, we traverse all the black cells, and then accumulate the number of black cells in each submatrix, recorded in the hash table
Finally, we traverse all the values in
Time complexity
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;
}