2768. Number of Black Blocks

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:

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.

Solution (Java)

import java.util.*;

class Solution {
    public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
        Map<Long, Integer> countMap = new HashMap<>(); // Map to store the count of black blocks
        List<Long> res = new ArrayList<>(5); // Result list to store the final counts

        for (int[] coor : coordinates) {
            int x = coor[0];
            int y = coor[1];

            for (int dx = 0; dx <= 1; dx++) {
                for (int dy = 0; dy <= 1; dy++) {
                    if (x - dx >= 0 && y - dy >= 0 && x - dx < m - 1 && y - dy < n - 1) {
                        // Calculate the key for the map using the coordinates
                        long key = (long) (x - dx) * n + y - dy;
                        countMap.put(key, countMap.getOrDefault(key, 0) + 1); // Increment the count of black blocks for the key
                    }
                }
            }
        }

        // Initialize the result array
        for (int i = 0; i < 5; i++) {
            res.add(0L);
        }

        // Iterate over the countMap and update the result list
        for (Map.Entry<Long, Integer> entry : countMap.entrySet()) {
            int count = entry.getValue();
            res.set(count, res.get(count) + 1); // Increment the count in the result list at the corresponding index
        }

        long sum = 0;
        for (long count : res) {
            sum += count;
        }

        res.set(0, 1L * (m - 1) * (n - 1) - sum); // Calculate the count of white blocks and store it at index 0

        // Convert the result list to an array
        long[] resultArray = new long[res.size()];
        for (int i = 0; i < res.size(); i++) {
            resultArray[i] = res.get(i);
        }

        return resultArray; // Return the final result array
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).