Problem Description

You have an m x n grid where cells can be either black or white. Initially, all cells are white. You're given a list of coordinates where each coordinate [x, y] indicates that the cell at position [x, y] is colored black.

A block is defined as a 2 x 2 submatrix within the grid. For a block with top-left corner at [x, y], it includes four cells:

• [x, y] (top-left)
• [x + 1, y] (bottom-left)
• [x, y + 1] (top-right)
• [x + 1, y + 1] (bottom-right)

Valid blocks must have their top-left corner at positions where 0 <= x < m - 1 and 0 <= y < n - 1 to ensure the entire 2 x 2 block fits within the grid.

Your task is to count how many blocks contain exactly 0, 1, 2, 3, and 4 black cells respectively. Return an array of size 5 where:

• arr[0] = number of blocks with 0 black cells
• arr[1] = number of blocks with 1 black cell
• arr[2] = number of blocks with 2 black cells
• arr[3] = number of blocks with 3 black cells
• arr[4] = number of blocks with 4 black cells

For example, if a 2 x 2 block has its top-left at [0, 0] and only the cell [0, 0] is black while cells [0, 1], [1, 0], and [1, 1] are white, then this block contains exactly 1 black cell.

The total number of possible 2 x 2 blocks in an m x n grid is (m - 1) × (n - 1).

Intuition

The key insight is that each black cell affects exactly 4 different 2 x 2 blocks. When we place a black cell at position (x, y), we need to think about which blocks this cell belongs to.

A cell at (x, y) can be:

• The top-left corner of a block starting at (x, y)
• The top-right corner of a block starting at (x, y-1)
• The bottom-left corner of a block starting at (x-1, y)
• The bottom-right corner of a block starting at (x-1, y-1)

So for each black cell, we can identify these 4 potential blocks it affects (as long as they're valid within the grid boundaries).

Instead of checking every possible 2 x 2 block in the grid (which would be (m-1) × (n-1) blocks), we can be more efficient. We only need to track the blocks that contain at least one black cell.

The approach is:

1. For each black cell, find all valid blocks it belongs to
2. Use a hash table to count how many black cells each affected block contains
3. The hash table key is the block's top-left corner (i, j), and the value is the count of black cells in that block

After processing all black cells, the hash table tells us exactly how many black cells each affected block contains. We can then count:

• Blocks with 1 black cell: count how many entries in the hash table have value 1
• Blocks with 2 black cells: count how many entries have value 2
• And so on...

For blocks with 0 black cells, we calculate: total possible blocks minus blocks that have at least one black cell, which is (m-1) × (n-1) - len(cnt).

This is efficient because we only process blocks that actually contain black cells, rather than checking all possible blocks in the grid.

Solution Approach

The solution uses a hash table to efficiently track blocks that contain black cells.

Step 1: Initialize a Counter We use a Counter (hash table) where keys are the top-left coordinates (i, j) of each block, and values are the count of black cells in that block.

Step 2: Process each black cell For each black cell at position (x, y), we need to identify all 2 x 2 blocks it belongs to. The code uses pairwise((0, 0, -1, -1, 0)) which generates pairs: (0, 0), (0, -1), (-1, -1), (-1, 0).

These offsets represent the four possible positions where the black cell can appear in a block:

• (x + 0, y + 0) → black cell is at top-left of block starting at (x, y)
• (x + 0, y + -1) → black cell is at top-right of block starting at (x, y-1)
• (x + -1, y + -1) → black cell is at bottom-right of block starting at (x-1, y-1)
• (x + -1, y + 0) → black cell is at bottom-left of block starting at (x-1, y)

For each potential block with top-left at (i, j), we check if it's valid: 0 <= i < m - 1 and 0 <= j < n - 1. If valid, we increment the counter for that block: cnt[(i, j)] += 1.

Step 3: Build the answer array Initialize ans = [0] * 5 to store the count of blocks with 0, 1, 2, 3, and 4 black cells.

Iterate through all values in the counter (which represent the number of black cells in each affected block). For each value x, increment ans[x] by 1.

Step 4: Calculate blocks with 0 black cells The total number of possible 2 x 2 blocks is (m - 1) * (n - 1). The counter only contains blocks with at least one black cell, so blocks with 0 black cells equals: ans[0] = (m - 1) * (n - 1) - len(cnt.values())

Time Complexity: O(k) where k is the number of coordinates, since we process each black cell once and each cell affects at most 4 blocks.

Space Complexity: O(k) for the hash table, which stores at most 4k entries.

Example Walkthrough

Let's walk through a concrete example with a 3 x 3 grid and coordinates [[0, 0], [1, 1], [2, 2]].

Initial Setup:

• Grid dimensions: m = 3, n = 3
• Total possible 2 x 2 blocks: (3-1) × (3-1) = 4 blocks
• These 4 blocks have top-left corners at: [0,0], [0,1], [1,0], [1,1]

Step 1: Process black cell at [0, 0]

The cell [0, 0] can be part of these blocks:

• Top-left of block at (0, 0) ✓ Valid (within bounds)
• Top-right of block at (0, -1) ✗ Invalid (j = -1 < 0)
• Bottom-right of block at (-1, -1) ✗ Invalid (i = -1 < 0)
• Bottom-left of block at (-1, 0) ✗ Invalid (i = -1 < 0)

Counter after this step: {(0, 0): 1}

Step 2: Process black cell at [1, 1]

The cell [1, 1] can be part of these blocks:

• Top-left of block at (1, 1) ✓ Valid
• Top-right of block at (1, 0) ✓ Valid
• Bottom-right of block at (0, 0) ✓ Valid
• Bottom-left of block at (0, 1) ✓ Valid

Counter after this step: {(0, 0): 2, (1, 1): 1, (1, 0): 1, (0, 1): 1}

Step 3: Process black cell at [2, 2]

The cell [2, 2] can be part of these blocks:

• Top-left of block at (2, 2) ✗ Invalid (i = 2 ≥ m-1)
• Top-right of block at (2, 1) ✗ Invalid (i = 2 ≥ m-1)
• Bottom-right of block at (1, 1) ✓ Valid
• Bottom-left of block at (1, 2) ✗ Invalid (j = 2 ≥ n-1)

Counter after this step: {(0, 0): 2, (1, 1): 2, (1, 0): 1, (0, 1): 1}

Step 4: Build the answer

From the counter:

• Block at (0, 0) has 2 black cells (cells [0,0] and [1,1])
• Block at (1, 1) has 2 black cells (cells [1,1] and [2,2])
• Block at (1, 0) has 1 black cell (cell [1,1])
• Block at (0, 1) has 1 black cell (cell [1,1])

Result array:

• ans[1] = 2 (blocks (1,0) and (0,1) each have 1 black cell)
• ans[2] = 2 (blocks (0,0) and (1,1) each have 2 black cells)
• ans[3] = 0 (no blocks with 3 black cells)
• ans[4] = 0 (no blocks with 4 black cells)
• ans[0] = 4 - 4 = 0 (total blocks - blocks with at least one black cell)

Final answer: [0, 2, 2, 0, 0]

Solution Implementation

Time and Space Complexity

The time complexity is O(l) where l is the length of coordinates. Each coordinate in the input list is processed once, and for each coordinate, we check at most 4 adjacent 2x2 blocks (the pairwise operation generates 4 pairs from the 5-element tuple). Each block check and counter update operation takes O(1) time. Therefore, the total time for processing all coordinates is O(4l) = O(l). The second loop iterates through the counter values, which contains at most 4l entries (since each coordinate can affect at most 4 blocks), taking O(l) time. The final calculation for ans[0] is O(1). Thus, the overall time complexity is O(l) + O(l) + O(1) = O(l).

The space complexity is O(l). The counter cnt stores the count of black cells for each affected 2x2 block. In the worst case, when coordinates are spread out such that no two coordinates affect the same 2x2 block, each coordinate can create up to 4 new entries in the counter. However, since we're counting unique blocks, the maximum number of entries in the counter is bounded by min(4l, (m-1)*(n-1)). For practical purposes and given that l is typically much smaller than m*n, the space complexity is O(l). The answer array ans uses constant space O(5) = O(1), so the overall space complexity is O(l).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Block Boundary Validation

A frequent mistake is incorrectly checking whether a 2x2 block fits within the grid boundaries. Developers often forget that for a block with top-left corner at (i, j), the bottom-right corner is at (i+1, j+1).

Incorrect approach:

# Wrong: checking if the black cell position is valid
if 0 <= x < m and 0 <= y < n:
    block_black_count[(x, y)] += 1

Correct approach:

# Right: checking if the entire 2x2 block fits in the grid
if 0 <= block_row < m - 1 and 0 <= block_col < n - 1:
    block_black_count[(block_row, block_col)] += 1

2. Duplicate Counting of Black Cells

Another pitfall is processing the same black cell multiple times if it appears multiple times in the coordinates list. This leads to incorrect counts.

Solution: Convert coordinates to a set first to remove duplicates:

unique_coordinates = set(map(tuple, coordinates))
for row, col in unique_coordinates:
    # Process each unique black cell

3. Misunderstanding Block-Cell Relationships

Many developers struggle with determining which blocks a given black cell belongs to. A black cell at (x, y) can be part of up to 4 different 2x2 blocks:

• Top-left position of block at (x, y)
• Top-right position of block at (x, y-1)
• Bottom-left position of block at (x-1, y)
• Bottom-right position of block at (x-1, y-1)

Visual representation:

For a black cell at (2, 2), it belongs to blocks with top-left at:
(2, 2) - cell is top-left
(2, 1) - cell is top-right
(1, 2) - cell is bottom-left
(1, 1) - cell is bottom-right

4. Off-by-One Error in Total Block Count

The total number of 2x2 blocks in an m x n grid is (m-1) × (n-1), not m × n or (m-2) × (n-2).

Why (m-1) × (n-1)?

• Valid top-left positions for rows: 0 to m-2 (total: m-1 positions)
• Valid top-left positions for columns: 0 to n-2 (total: n-1 positions)
• Total blocks: (m-1) × (n-1)

5. Forgetting to Handle Edge Cases

Edge cases to consider:

• Empty coordinates list (all cells are white)
• Grid too small to contain any 2x2 blocks (m < 2 or n < 2)
• All cells are black

Robust implementation:

def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:
    # Handle edge case: grid too small
    if m < 2 or n < 2:
        return [0, 0, 0, 0, 0]
  
    # Handle empty coordinates
    if not coordinates:
        return [(m-1)*(n-1), 0, 0, 0, 0]
  
    # Main logic continues...