2768. Number of Black Blocks - Detailed Explanation
Problem Statement
Description
You have an m × n grid initially filled with white cells. You are given a list of black cell coordinates. A 2×2 block is any submatrix of size 2 rows by 2 columns. For each k from 0 to 4, determine how many 2×2 blocks contain exactly k black cells, and return an array ans of length 5 where ans[k] is the count for k black cells.
Examples
Example 1
Input
m = 2, n = 2
blackCells = [[0,0]]
Output
[0,1,0,0,0]
Explanation
There is exactly one 2×2 block (covering the whole grid). It has 1 black cell, so ans[1] = 1.
Example 2
Input
m = 3, n = 3
blackCells = [[0,0],[0,1],[1,1]]
Output
[0,2,1,1,0]
Explanation
The four 2×2 blocks have black‐cell counts {3,2,1,1}, so ans = [0,2,1,1,0].
Example 3
Input
m = 4, n = 4
blackCells = [[0,0],[0,1],[1,2],[3,3]]
Output
[3,4,2,0,0]
Explanation
There are 9 blocks; counts are {2,2,1,1,1,1,0,0,0}.
Constraints
- 1 ≤ m, n ≤ 10^9
- 0 ≤ blackCells.length ≤ 10^4
- blackCells[i].length = 2
- 0 ≤ blackCells[i][0] < m
- 0 ≤ blackCells[i][1] < n
- All blackCells are unique
Hints
- For each black cell, which 2×2 blocks can it belong to?
- Can you count contributions to each block instead of scanning every block in the grid?
Brute Force Approach
Idea
Check every possible 2×2 block, count its black cells by inspecting the four positions.
Steps
- Initialize ans = [0,0,0,0,0].
- For r in [0..m-2], for c in [0..n-2]:
- Count blacks among (r,c), (r,c+1), (r+1,c), (r+1,c+1).
- Increment ans[count].
Code (Python)
Code (Java)
Complexity Analysis
- Time: O(K) where K = number of blackCells (each contributes up to 4 map updates)
- Space: O(K) for storing only blocks that have ≥1 black cell
Step‑by‑Step Walkthrough and Visual Example
Consider m=3, n=3, blackCells=[[0,0],[0,1],[1,1]].
The grid (B = black, . = white):
B B .
. B .
. . .
Black at (0,0) affects blocks with top‑left at (0,0) and (0,−1/−1 invalid)
Black at (0,1) affects (0,0) and (0,1)
Black at (1,1) affects (0,0),(0,1),(1,0),(1,1)
Map counts:
- (0,0) → 3
- (0,1) → 2
- (1,0) → 1
- (1,1) → 1
Total blocks = 4, so ans[0] = 4−4 = 0
Then ans[1]=2, ans[2]=1, ans[3]=1, ans[4]=0
Common Mistakes
- Forgetting to check block boundaries (r<0 or c<0).
- Using
intfor total blocks when m,n are large—overflow risk. - Double‑counting blocks when a black cell is on multiple edges.
Edge Cases
- No black cells → all blocks have 0 blacks.
- m<2 or n<2 → no 2×2 blocks exist, return [0,0,0,0,0].
- All cells black → ans[4] = (m−1)*(n−1).
Alternative Variations
- Count k×k submatrices with exactly t black cells.
- Sliding‐window sum queries over sparse matrices.
Related Problems
GET YOUR FREE
Coding Questions Catalog
