Problem

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 a0-indexed integer array arr of size 5 such that arr[i] is the number of blocks that contains exactly i black cells.

Examples

Example 1

1
2
3
4
5
6
7

Input: m = 3, n = 3, coordinates = [[0,0]]
Output: [3,1,0,0,0]
Explanation: The grid looks like this:
![](https://assets.leetcode.com/uploads/2023/06/18/screen-shot-2023-06-18-at-44656-am.png)
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

1
2
3
4
5
6
7

Input: m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
Output: [0,2,2,0,0]
Explanation: The grid looks like this:
![](https://assets.leetcode.com/uploads/2023/06/18/screen-shot-2023-06-18-at-45018-am.png)
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 <= 10^5
  • 2 <= n <= 10^5
  • 0 <= coordinates.length <= 10^4
  • coordinates[i].length == 2
  • 0 <= coordinates[i][0] < m
  • 0 <= coordinates[i][1] < n
  • It is guaranteed that coordinates contains pairwise distinct coordinates.

Solution

Method 1 – Hash Map for Block Counting

Intuition

Each black cell affects up to 4 blocks (top-left corners). For each black cell, increment the count for each block it belongs to. Count blocks by number of black cells.

Approach

  1. For each black cell, for each of its up to 4 possible blocks, increment a hash map counter.
  2. For all blocks, count how many have 0, 1, 2, 3, or 4 black cells.
  3. Total blocks = (m-1)*(n-1). Subtract blocks with black cells to get count of blocks with 0 black cells.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    vector<long long> countBlackBlocks(int m, int n, vector<vector<int>>& coordinates) {
        unordered_map<long long, int> cnt;
        for (auto& c : coordinates) {
            int x = c[0], y = c[1];
            for (int dx = 0; dx <= 1; ++dx)
                for (int dy = 0; dy <= 1; ++dy) {
                    int i = x-dx, j = y-dy;
                    if (i >= 0 && j >= 0 && i < m-1 && j < n-1)
                        cnt[(long long)i*n+j]++;
                }
        }
        vector<long long> res(5);
        for (auto& [_, v] : cnt) res[v]++;
        res[0] = (long long)(m-1)*(n-1) - cnt.size();
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func countBlackBlocks(m, n int, coordinates [][]int) []int64 {
    cnt := map[int64]int{}
    for _, c := range coordinates {
        x, y := c[0], c[1]
        for dx := 0; dx <= 1; dx++ {
            for dy := 0; dy <= 1; dy++ {
                i, j := x-dx, y-dy
                if i >= 0 && j >= 0 && i < m-1 && j < n-1 {
                    key := int64(i)*int64(n)+int64(j)
                    cnt[key]++
                }
            }
        }
    }
    res := make([]int64, 5)
    for _, v := range cnt { res[v]++ }
    res[0] = int64((m-1)*(n-1)) - int64(len(cnt))
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.*;
class Solution {
    public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
        Map<Long, Integer> cnt = new HashMap<>();
        for (int[] c : coordinates) {
            int x = c[0], y = c[1];
            for (int dx = 0; dx <= 1; ++dx)
                for (int dy = 0; dy <= 1; ++dy) {
                    int i = x-dx, j = y-dy;
                    if (i >= 0 && j >= 0 && i < m-1 && j < n-1)
                        cnt.put((long)i*n+j, cnt.getOrDefault((long)i*n+j, 0)+1);
                }
        }
        long[] res = new long[5];
        for (int v : cnt.values()) res[v]++;
        res[0] = (long)(m-1)*(n-1) - cnt.size();
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun countBlackBlocks(m: Int, n: Int, coordinates: Array<IntArray>): LongArray {
        val cnt = mutableMapOf<Long, Int>()
        for (c in coordinates) {
            val x = c[0]; val y = c[1]
            for (dx in 0..1) for (dy in 0..1) {
                val i = x-dx; val j = y-dy
                if (i >= 0 && j >= 0 && i < m-1 && j < n-1)
                    cnt[i.toLong()*n+j] = cnt.getOrDefault(i.toLong()*n+j, 0)+1
            }
        }
        val res = LongArray(5)
        for (v in cnt.values) res[v]++
        res[0] = (m-1).toLong()*(n-1) - cnt.size
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:
        from collections import Counter
        cnt = Counter()
        for x, y in coordinates:
            for dx in range(2):
                for dy in range(2):
                    i, j = x-dx, y-dy
                    if 0 <= i < m-1 and 0 <= j < n-1:
                        cnt[i*n+j] += 1
        res = [0]*5
        for v in cnt.values(): res[v] += 1
        res[0] = (m-1)*(n-1) - len(cnt)
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

use std::collections::HashMap;
impl Solution {
    pub fn count_black_blocks(m: i32, n: i32, coordinates: Vec<Vec<i32>>) -> Vec<i64> {
        let mut cnt = HashMap::new();
        for c in coordinates {
            let x = c[0]; let y = c[1];
            for dx in 0..=1 {
                for dy in 0..=1 {
                    let i = x-dx; let j = y-dy;
                    if i >= 0 && j >= 0 && i < m-1 && j < n-1 {
                        let key = (i as i64)*n as i64 + j as i64;
                        *cnt.entry(key).or_insert(0) += 1;
                    }
                }
            }
        }
        let mut res = vec![0i64; 5];
        for v in cnt.values() { res[*v as usize] += 1; }
        res[0] = (m as i64-1)*(n as i64-1) - cnt.len() as i64;
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

Complexity

  • ⏰ Time complexity: O(K) (K = number of black cells)
  • 🧺 Space complexity: O(K)