2768. Number of Black Blocks LeetCode Solution
In this guide, you will get 2768. Number of Black Blocks LeetCode Solution with the best time and space complexity. The solution to Number of Black Blocks problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Number of Black Blocks solution in C++
- Number of Black Blocks solution in Java
- Number of Black Blocks solution in Python
- Additional Resources

Problem Statement of Number of Black Blocks
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.
Complexity Analysis
- Time Complexity: O(|\texttt{coordinates}|)
- Space Complexity: O(|\texttt{coordinates}|)
2768. Number of Black Blocks LeetCode Solution in C++
class Solution {
public:
vector<long long> countBlackBlocks(int m, int n,
vector<vector<int>>& coordinates) {
vector<long long> ans(5);
// count[i * n + j] := the number of black cells in
// (i - 1, j - 1), (i - 1, j), (i, j - 1), (i, j)
unordered_map<long, int> count;
for (const vector<int>& coordinate : coordinates) {
const int x = coordinate[0];
const int y = coordinate[1];
for (long i = x; i < x + 2; ++i)
for (long j = y; j < y + 2; ++j)
// 2 x 2 submatrix with right-bottom conner being (i, j) contains the
// current black cell (x, y).
if (i - 1 >= 0 && i < m && j - 1 >= 0 && j < n)
++count[i * n + j];
}
for (const auto& [_, freq] : count)
++ans[freq];
ans[0] = (m - 1L) * (n - 1) - accumulate(ans.begin(), ans.end(), 0L);
return ans;
}
};
/* code provided by PROGIEZ */
2768. Number of Black Blocks LeetCode Solution in Java
class Solution {
public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
long[] ans = new long[5];
// count[i * n + j] := the number of black cells in
// (i - 1, j - 1), (i - 1, j), (i, j - 1), (i, j)
Map<Long, Integer> count = new HashMap<>();
for (int[] coordinate : coordinates) {
final int x = coordinate[0];
final int y = coordinate[1];
for (long i = x; i < x + 2; ++i)
for (long j = y; j < y + 2; ++j)
// 2 x 2 submatrix with right-bottom conner being (i, j) contains the
// current black cell (x, y).
if (i - 1 >= 0 && i < m && j - 1 >= 0 && j < n)
count.merge(i * n + j, 1, Integer::sum);
}
for (final int freq : count.values())
++ans[freq];
ans[0] = (m - 1L) * (n - 1) - Arrays.stream(ans).sum();
return ans;
}
}
// code provided by PROGIEZ
2768. Number of Black Blocks LeetCode Solution in Python
class Solution:
def countBlackBlocks(
self,
m: int,
n: int,
coordinates: list[list[int]],
) -> list[int]:
ans = [0] * 5
# count[i * n + j] := the number of black cells in
# (i - 1, j - 1), (i - 1, j), (i, j - 1), (i, j)
count = collections.Counter()
for x, y in coordinates:
for i in range(x, x + 2):
for j in range(y, y + 2):
# 2 x 2 submatrix with right-bottom conner being (i, j) contains the
# current black cell (x, y).
if 0 < i < m and 0 < j < n:
count[(i, j)] += 1
for freq in count.values():
ans[freq] += 1
ans[0] = (m - 1) * (n - 1) - sum(ans)
return ans
# code by PROGIEZ
Additional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.