LeetCode 2768 - Number of Black Blocks

This problem asks us to count the number of 2 x 2 blocks in a grid based on how many black cells they contain. We are given the dimensions of a grid, m rows and n columns, and a list of coordinates representing black cells. Every cell not listed is white.

leetcodemediumarrayhash-tableenumeration

LeetCode Problem 2768

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Enumeration

Solution

Problem Understanding

This problem asks us to count the number of 2 x 2 blocks in a grid based on how many black cells they contain. We are given the dimensions of a grid, m rows and n columns, and a list of coordinates representing black cells. Every cell not listed is white. A block is a 2 x 2 submatrix defined by its top-left corner, and we need to determine how many blocks contain 0, 1, 2, 3, or 4 black cells. The output is a 5-element array where arr[i] is the number of blocks containing exactly i black cells.

The problem constraints are significant: m and n can be up to 10^5, meaning the total number of cells could be as high as 10^10. We cannot construct the full grid or enumerate every block. The coordinates array is much smaller (≤ 10^4), which suggests that an optimal solution must focus only on blocks affected by black cells rather than iterating over the entire grid.

Important edge cases include when coordinates is empty (all blocks are white), when black cells are at edges (some 2 x 2 blocks are partially outside the grid and should be ignored), and when multiple black cells influence the same block.

Approaches

The brute-force approach would be to construct the entire m x n grid and iterate over every 2 x 2 block, counting black cells in each block. This gives correct results but is infeasible because the grid size could reach 10^10, far beyond memory and time limits.

The optimal approach leverages the insight that only blocks containing at least one black cell need explicit counting. Each black cell can affect at most four 2 x 2 blocks (the block where it is top-left, top-right, bottom-left, or bottom-right). We can use a hash map to track counts of black cells for each affected block. After processing all black cells, the remaining blocks are all white, and we can compute their count with simple arithmetic.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n) O(m * n) Iterate over every block in the full grid
Optimal O(k) O(k) Only process blocks affected by k = len(coordinates) black cells, then compute remaining white blocks

Algorithm Walkthrough

  1. Initialize a dictionary block_counts to map the top-left coordinate of each block to the number of black cells in that block.
  2. For each black cell (x, y) in coordinates, determine which 2 x 2 blocks it contributes to. These blocks have top-left corners at (x-1, y-1), (x-1, y), (x, y-1), (x, y). Skip blocks that would be outside the grid.
  3. Increment the black cell count for each valid block in block_counts.
  4. Initialize an array arr of size 5 with zeros to store the counts of blocks with 0, 1, 2, 3, or 4 black cells.
  5. Iterate over the values in block_counts and increment arr[count] where count is the number of black cells in that block.
  6. Compute the total number of blocks in the grid as (m-1)*(n-1). The number of blocks with 0 black cells is the difference between this total and the sum of blocks with 1-4 black cells.
  7. Set arr[0] to this number and return arr.

Why it works: Every block is either affected by at least one black cell or it is entirely white. By counting affected blocks using a hash map and calculating white blocks with arithmetic, we guarantee every block is counted exactly once.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:
        block_counts = defaultdict(int)
        
        for x, y in coordinates:
            for dx in [0, -1]:
                for dy in [0, -1]:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m - 1 and 0 <= ny < n - 1:
                        block_counts[(nx, ny)] += 1
        
        arr = [0] * 5
        for count in block_counts.values():
            arr[count] += 1
        
        total_blocks = (m - 1) * (n - 1)
        arr[0] = total_blocks - sum(arr[1:])
        return arr

This Python implementation uses a defaultdict to count black cells per block. The nested loops over [0, -1] adjust the top-left coordinates of affected blocks. After processing all black cells, we populate the array arr based on the number of black cells per block. Finally, we compute the number of fully white blocks using the total block count minus blocks with at least one black cell.

Go Solution

func countBlackBlocks(m int, n int, coordinates [][]int) []int64 {
    type point struct{ x, y int }
    blockCounts := make(map[point]int)
    
    for _, c := range coordinates {
        x, y := c[0], c[1]
        for _, dx := range []int{0, -1} {
            for _, dy := range []int{0, -1} {
                nx, ny := x+dx, y+dy
                if nx >= 0 && nx < m-1 && ny >= 0 && ny < n-1 {
                    p := point{nx, ny}
                    blockCounts[p]++
                }
            }
        }
    }
    
    arr := make([]int64, 5)
    for _, count := range blockCounts {
        arr[count]++
    }
    
    totalBlocks := int64((m - 1) * (n - 1))
    sumNonZero := int64(0)
    for i := 1; i <= 4; i++ {
        sumNonZero += arr[i]
    }
    arr[0] = totalBlocks - sumNonZero
    
    return arr
}

The Go implementation mirrors the Python logic. A custom point struct is used as the map key, and int64 is used for the return array to handle large numbers of blocks. Nested loops adjust block coordinates, and the final computation accounts for all white blocks.

Worked Examples

Example 1: m = 3, n = 3, coordinates = [[0,0]]

Block top-left Black cells
(0,0) 1
(0,1) 0
(1,0) 0
(1,1) 0

Array: [3,1,0,0,0]

Example 2: m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]

Block top-left Black cells
(0,0) 2
(0,1) 2
(1,0) 1
(1,1) 1

Array: [0,2,2,0,0]

Complexity Analysis

Measure Complexity Explanation
Time O(k) Each black cell affects up to 4 blocks, k = len(coordinates)
Space O(k) Store counts for affected blocks, at most 4*k entries

This is efficient because k is much smaller than m*n, avoiding full grid construction.

Test Cases

# Provided examples
assert Solution().countBlackBlocks(3, 3, [[0,0]]) == [3,1,0,0,0]  # single black cell
assert Solution().countBlackBlocks(3, 3, [[0,0],[1,1],[0,2]]) == [0,2,2,0,0]  # multiple black cells

# Edge cases
assert Solution().countBlackBlocks(2, 2, []) == [1,0,0,0,0]  # smallest grid, no black cells
assert Solution().countBlackBlocks(2, 2, [[0,0]]) == [0,1,0,0,0]  # smallest grid, one black cell
assert Solution().countBlackBlocks(3, 3, [[0,0],[0,1],[1,0],[1,1]]) == [0,0,0,0,1]  # block fully black
assert Solution().countBlackBlocks(3, 3, [[2,2]]) == [3,1,0,0,0]  # black at bottom-right, affects only one block
Test Why
single black cell basic counting
multiple black cells overlapping blocks
smallest grid empty handles minimal input
smallest grid one black minimal input with black
full black block block with 4 black cells
black at corner edge handling

Edge Cases

Empty coordinates: When no black cells exist, all blocks are white. The algorithm correctly computes the total