#2768

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Number of Black Blocks

Calculate the number of black blocks in a grid given a list of black cell coordinates.

Problem Statement

You are given a 0-indexed m x n grid, and a list of black cell coordinates. A block is defined as a 2x2 submatrix where the top-left cell is within the grid's bounds. The task is to count how many black cells are present in each block across the entire grid.

Given the coordinates of the black cells, determine the number of black cells for every possible 2x2 block in the grid. Return the count of black cells in each block, ensuring that you handle large grids efficiently by focusing on sparse black cells.

Examples

Example 1

Input: m = 3, n = 3, coordinates = [[0,0]]

Output: [3,1,0,0,0]

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]

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 Approach

Array Scanning

Start by iterating over all possible 2x2 blocks in the grid. For each block, check if the coordinates of black cells fall within the block's boundaries. This approach works well with sparse black cells.

Hash Set Lookup

To improve the lookup speed, store all the black cell coordinates in a hash set. For each block, check how many of the four potential cells in the block are black by querying the hash set. This reduces the time complexity of each lookup.

Optimizing for Large Grids

For very large grids (e.g., m and n up to 105), avoid checking all 2x2 blocks explicitly. Instead, optimize by only considering blocks that have at least one black cell in them, utilizing the black cell coordinates directly.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of black cells and the number of 2x2 blocks considered. With hash set lookups, checking each block for black cells is efficient. Space complexity is O(k), where k is the number of black cells, due to the hash set storage.

What Interviewers Usually Probe

The candidate demonstrates knowledge of hashing and efficient lookups.
The candidate avoids checking unnecessary blocks in large grids.
The candidate uses array scanning effectively, even for large inputs.

Common Pitfalls or Variants

Common pitfalls

Not utilizing a hash set to optimize lookups for black cell coordinates.
Iterating over every possible block without considering the sparsity of black cells.
Failing to handle edge cases where the number of blocks is large but the number of black cells is small.

Follow-up variants

Consider variations where black cells are clustered, affecting the distribution of black cells across blocks.
Expand the problem to work with grids that may have a non-square shape.
Modify the problem to count the number of white cells instead of black cells.

FAQ

How do I efficiently solve the 'Number of Black Blocks' problem?

Use array scanning to iterate over all blocks and hash sets to optimize lookup of black cells within each block.

What data structure should I use to store black cell coordinates?

Use a hash set to store the coordinates of black cells, ensuring constant-time lookups when checking each block.

How do I handle large grids in the 'Number of Black Blocks' problem?

Focus only on blocks that contain black cells, reducing the number of blocks you need to check.

What is the time complexity of the optimal solution?

The time complexity is O(k + m n), where k is the number of black cells and m n is the number of blocks in the grid.

Can I modify the 'Number of Black Blocks' problem for non-square grids?

Yes, the approach can be adapted to handle grids with non-square dimensions by adjusting the block boundaries accordingly.

terminal

Solution

Solution 1: Hash Table

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

Continue Practicing

#2605 form smallest number from two digit arrays #2975 maximum square area by removing fences from a field #3020 find the maximum number of elements in subset