Number of Black Blocks
MediumUpdated: Aug 2, 2025
Practice on:
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
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 <= 10^52 <= n <= 10^50 <= coordinates.length <= 10^4coordinates[i].length == 20 <= coordinates[i][0] < m0 <= coordinates[i][1] < n- It is guaranteed that
coordinatescontains 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
- For each black cell, for each of its up to 4 possible blocks, increment a hash map counter.
- For all blocks, count how many have 0, 1, 2, 3, or 4 black cells.
- Total blocks = (m-1)*(n-1). Subtract blocks with black cells to get count of blocks with 0 black cells.
Code
C++
#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;
}
};
Go
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
}
Java
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;
}
}
Kotlin
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
}
}
Python
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
Rust
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
}
}
TypeScript
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)