# Number of Black Blocks
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-black-blocks)
Canonical: https://scaleengineer.com/dsa/problems/number-of-black-blocks
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Hash Table
**Companies:** [Visa](https://scaleengineer.com/companies/visa), [Capital One](https://scaleengineer.com/companies/capital-one), [X](https://scaleengineer.com/companies/x), [SIG](https://scaleengineer.com/companies/sig), [Block](https://scaleengineer.com/companies/block)
---
## 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 _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:
![](https://assets.glich.co/dsa/number-of-black-blocks/image0.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:**

**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.glich.co/dsa/number-of-black-blocks/image1.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 <= 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.

# Approaches
## Brute-Force Grid Traversal
This approach involves iterating through every possible 2x2 block in the grid. For each block, we count the number of black cells it contains and update our result array accordingly. This is a straightforward but highly inefficient method given the potential size of the grid.
**Time:** O(m * n + C), where C is the number of black cells. `O(C)` to populate the `HashSet` and `O(m * n)` to iterate through all blocks. Given `m, n` up to 10^5, this is too slow. · **Space:** O(C), where C is the number of black cells. This space is used to store the black cell coordinates in the `HashSet`.
**Pros:** Simple to understand and implement.; Correct for small grids.
**Cons:** Extremely inefficient for large grids.; Will result in a "Time Limit Exceeded" error on platforms like LeetCode due to the `m * n` loop.
### Explanation
First, we need an efficient way to check if a given cell is black. We can store all the black cell coordinates from the `coordinates` array into a `HashSet` for average O(1) lookup time. To store a 2D coordinate `[r, c]` in the set, we can encode it into a single `long` value, for instance, `(long)r * n + c`, to avoid issues with hashing arrays or custom pair objects.

We initialize a result array `ans` of size 5 with all zeros.

The core of the algorithm is a nested loop that iterates through all possible top-left corners `[r, c]` of a 2x2 block. The row `r` goes from `0` to `m-2`, and the column `c` goes from `0` to `n-2`.

Inside the loop, for each block, we check its four cells: `[r, c]`, `[r+1, c]`, `[r, c+1]`, and `[r+1, c+1]`. We count how many of these are present in our `HashSet` of black cells.

Let's say we find `k` black cells in the current block. We then increment `ans[k]`. Note that we only update counts for blocks with `k > 0` to simplify the final calculation for `ans[0]`.

After iterating through all `(m-1) * (n-1)` blocks, the array `ans` will contain the counts for blocks with 1, 2, 3, and 4 black cells. The count for blocks with 0 black cells is not yet correct.

The total number of 2x2 blocks is `(long)(m-1) * (n-1)`. The number of blocks with at least one black cell is the sum `ans[1] + ans[2] + ans[3] + ans[4]`. Therefore, the number of blocks with zero black cells is `ans[0] = totalBlocks - (ans[1] + ans[2] + ans[3] + ans[4])`.

Finally, we return the `ans` array.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
        Set<Long> blackCells = new HashSet<>();
        for (int[] coord : coordinates) {
            long r = coord[0];
            long c = coord[1];
            blackCells.add(r * n + c);
        }

        long[] ans = new long[5];
        // This loop is too slow for the given constraints
        for (int r = 0; r < m - 1; r++) {
            for (int c = 0; c < n - 1; c++) {
                int blackCount = 0;
                if (blackCells.contains((long)r * n + c)) blackCount++;
                if (blackCells.contains((long)(r + 1) * n + c)) blackCount++;
                if (blackCells.contains((long)r * n + (c + 1))) blackCount++;
                if (blackCells.contains((long)(r + 1) * n + (c + 1))) blackCount++;
                
                if (blackCount > 0) {
                    ans[blackCount]++;
                }
            }
        }

        long totalBlocks = (long)(m - 1) * (n - 1);
        long nonZeroBlocks = 0;
        for (int i = 1; i < 5; i++) {
            nonZeroBlocks += ans[i];
        }
        ans[0] = totalBlocks - nonZeroBlocks;

        return ans;
    }
}
```
### Algorithm
- Create a `HashSet` to store the coordinates of all black cells for quick lookups.
- Initialize a result array `ans` of size 5 to all zeros.
- Iterate through each possible top-left corner `(r, c)` of a 2x2 block, where `0 <= r < m-1` and `0 <= c < n-1`.
- For each block, count the number of black cells (`k`) it contains by checking its four cells against the `HashSet`.
- If `k > 0`, increment `ans[k]`.
- Calculate the total number of blocks: `total = (m-1) * (n-1)`.
- Calculate the number of blocks with zero black cells: `ans[0] = total - (ans[1] + ans[2] + ans[3] + ans[4])`.
- Return the `ans` array.

## Optimized Approach using HashMap
This efficient approach avoids iterating through the entire grid. Instead, it focuses only on the black cells. The key insight is that a single black cell can only affect a maximum of four 2x2 blocks. By iterating through each black cell and updating a count for the blocks it influences, we can solve the problem in time proportional to the number of black cells, not the grid size.
**Time:** O(C), where C is the number of black cells (`coordinates.length`). For each of the `C` cells, we perform a constant number of operations (4 lookups/updates in the HashMap). Iterating through the map at the end takes `O(K)` time, where `K` is the number of affected blocks (`K <= 4*C`). Thus, the total time complexity is linear with respect to the number of black cells. · **Space:** O(C), where C is the number of black cells (`coordinates.length`). The `HashMap` can store up to `4*C` entries in the worst case, where each black cell affects four distinct blocks. Therefore, the space required is proportional to the number of black cells.
**Pros:** Highly efficient, with performance depending on the number of black cells, not the grid size.; Handles the large constraints on `m` and `n` effectively.; Optimal solution for this problem.
**Cons:** Slightly more complex to conceptualize than the brute-force approach.; Requires careful handling of coordinates and boundary checks.
### Explanation
The main idea is to count the number of black cells for every block that contains at least one black cell. Blocks with zero black cells can be calculated at the end.

We use a `HashMap` where the key represents a 2x2 block and the value stores the number of black cells in it. A block is uniquely identified by its top-left corner `(r, c)`. We can encode this 2D coordinate into a single `long` value (e.g., `(long)r * n + c`) to use as the map key.

We iterate through each black cell `(r, c)` from the `coordinates` input.

For each black cell `(r, c)`, it can be part of four potential 2x2 blocks. These blocks would have their top-left corners at:
1.  `(r, c)`
2.  `(r, c-1)`
3.  `(r-1, c)`
4.  `(r-1, c-1)`

For each of these four potential top-left corners `(tr, tc)`, we first check if it's a valid corner for a block within the grid (i.e., `0 <= tr < m-1` and `0 <= tc < n-1`).

If `(tr, tc)` is a valid top-left corner, it means the block starting there is affected by the current black cell. We increment the black cell count for this block in our `HashMap`. We use `map.getOrDefault(key, 0) + 1` to handle both existing and new entries.

After processing all black cells, the `HashMap` will contain every block that has one or more black cells, mapped to its respective black cell count.

We then initialize our result array `ans` of size 5. We iterate through the values of the `HashMap`. For each count `k`, we increment `ans[k]`.

The total number of 2x2 blocks in the grid is `(long)(m - 1) * (n - 1)`. The number of blocks with at least one black cell is simply the size of our `HashMap`.

The number of blocks with zero black cells is the total number of blocks minus the number of blocks with at least one black cell. So, `ans[0] = totalBlocks - map.size()`.

Finally, we return the `ans` array.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
        Map<Long, Integer> blockCounts = new HashMap<>();
        
        for (int[] coord : coordinates) {
            int r = coord[0];
            int c = coord[1];
            
            // A black cell at (r, c) can affect up to 4 blocks.
            // We check the 2x2 area around the black cell.
            // The top-left corners of these potential blocks are:
            // (r-1, c-1), (r-1, c), (r, c-1), (r, c)
            for (int i = r - 1; i <= r; i++) {
                for (int j = c - 1; j <= c; j++) {
                    // Check if (i, j) is a valid top-left corner of a 2x2 block
                    if (i >= 0 && i < m - 1 && j >= 0 && j < n - 1) {
                        long blockId = (long)i * n + j;
                        blockCounts.put(blockId, blockCounts.getOrDefault(blockId, 0) + 1);
                    }
                }
            }
        }
        
        long[] ans = new long[5];
        long nonZeroBlocks = blockCounts.size();
        
        for (int count : blockCounts.values()) {
            if (count > 0 && count <= 4) {
                ans[count]++;
            }
        }
        
        long totalBlocks = (long)(m - 1) * (n - 1);
        ans[0] = totalBlocks - nonZeroBlocks;
        
        return ans;
    }
}
```
### Algorithm
- Initialize a `HashMap<Long, Integer>` called `blockCounts` to store the number of black cells for each affected block.
- Iterate through each black cell `(r, c)` in the `coordinates` array.
- For each black cell, consider the four potential 2x2 blocks it can belong to (those with top-left corners at `(r, c)`, `(r, c-1)`, `(r-1, c)`, and `(r-1, c-1)`).
- For each of these four potential blocks, if its top-left corner `(tr, tc)` is valid (`0 <= tr < m-1` and `0 <= tc < n-1`), increment its count in the `blockCounts` map.
- After iterating through all black cells, initialize a result array `ans` of size 5.
- Iterate through the values in `blockCounts`. For each value `k`, increment `ans[k]`.
- Calculate the total number of blocks: `total = (long)(m - 1) * (n - 1)`.
- The number of blocks with at least one black cell is `blockCounts.size()`.
- Calculate the number of blocks with zero black cells: `ans[0] = total - blockCounts.size()`.
- Return the `ans` array.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```