2768. Number of Black Blocks

SourceBiweekly Contest 108 Q4DifficultyMediumRating2175

Description

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 <= 10⁵
2 <= n <= 10⁵
0 <= coordinates.length <= 10⁴
coordinates[i].length == 2
0 <= coordinates[i][0] < m
0 <= coordinates[i][1] < n
It is guaranteed that coordinates contains pairwise distinct coordinates.

Solutions

Solution 1: Hash Table

Thinking

Count how many \(2\times 2\) blocks contain \(0\) through \(4\) black cells. There are \((m-1)(n-1)\) blocks and the grid can be \(10^5\) on a side, so the blocks cannot all be visited.

A black cell touches at most four blocks. Increment those blocks in a hash map, fill \(\textit{ans}[1..4]\) from the map values, and set \(\textit{ans}[0]\) to the number of blocks minus the map size.

For each \(2 \times 2\) submatrix, we can use its upper-left corner coordinate \((x, y)\) to represent it.

For each black cell \((x, y)\), its contribution to the 4 submatrices is \(1\), namely the matrices \((x - 1, y - 1)\), \((x - 1, y)\), \((x, y - 1)\), \((x, y)\).

Therefore, we traverse all the black cells, and then accumulate the number of black cells in each submatrix, recorded in the hash table \(\textit{cnt}\).

Finally, we traverse all the values in \(\textit{cnt}\) (greater than \(0\)), count the number of times they appear, and record them in the answer array \(\textit{ans}\), while \(\textit{ans}[0]\) represents the number of submatrices without black cells, the value is \((m - 1) \times (n - 1) - \sum_{i = 1}^4 \textit{ans}[i]\).

The time complexity is \(O(l)\), and the space complexity is \(O(l)\), where \(l\) is the length of \(\textit{coordinates}\).

Python3JavaC++GoTypeScript

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

2768. Number of Black Blocks

Description

Solutions

Solution 1: Hash Table

Comments