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 <= 1052 <= n <= 1050 <= coordinates.length <= 104coordinates[i].length == 20 <= coordinates[i][0] < m0 <= coordinates[i][1] < ncoordinates contains pairwise distinct coordinates.Problem Overview: You are given an m x n grid where some cells are black. The task is to count how many 2 x 2 subgrids contain exactly 0, 1, 2, 3, or 4 black cells. The result is a frequency array of size five representing each possible count.
Approach 1: Brute Force Enumeration (Time: O((m-1)*(n-1)), Space: O(k))
Iterate over every possible 2 x 2 block in the grid. For each block, check the four cell coordinates and determine how many are black. A set or hash structure stores the given black cell coordinates so each lookup is O(1). Since there are (m-1)*(n-1) blocks and each block checks four cells, the work per block is constant. This method is straightforward and easy to reason about, but it becomes inefficient when the grid is extremely large while the number of black cells is small.
Approach 2: HashMap Counting by Black Cell Contribution (Time: O(k), Space: O(k))
Instead of scanning every block, iterate only through the given black cells. Each black cell can belong to at most four different 2 x 2 blocks (top-left positions at (r-1,c-1), (r-1,c), (r,c-1), and (r,c)). For each valid block position inside the grid bounds, increment a counter in a hash map keyed by the block's top-left coordinate. After processing all black cells, the map tells you how many black cells appear in each affected block. Remaining blocks automatically have zero black cells. This approach leverages hash table counting and enumeration of neighboring positions, reducing work to only the blocks influenced by black cells.
Recommended for interviews: The hash map contribution approach is the expected solution. It scales with the number of black cells rather than the grid size, achieving O(k) time where k is the number of black cells. Interviewers often accept the brute force explanation first because it shows clear understanding of the grid structure, but the optimized method demonstrates stronger problem solving with array coordinate reasoning and constant‑time hash updates.
This approach involves iterating over each possible 2x2 block and counting the number of black cells within it. Create a grid based on the given dimensions and color the cells black as per the 'coordinates' input. For each top-left position in a potential 2x2 block, check the color of the four cells in the block and maintain a count of blocks with 0 to 4 black cells.
The function initializes a grid of size mxn and marks the cells outlined in 'coordinates' as black. For each possible top-left corner of a 2x2 block in the grid (ensuring it stays within bounds), it counts how many of those four cells are black. It increments the count of that particular black count in a result array of size 5.
Python
JavaScript
Time Complexity: O(m*n), where m is the number of rows and n is the number of columns in the grid.
Space Complexity: O(m*n) for storing the grid.
Instead of building the entire grid, an efficient approach is to use a HashMap (or dictionary) to directly map the top-left corner of each 2x2 block potentially impacted by each black cell. For each black cell, adjust counts in the HashMap for all blocks it can affect, and finally tally results into a count array of size 5 for the output.
Rather than populating a grid, we use a dictionary to keep track of the count of black cells in each possible block. For each black cell, we attempt to update up to 4 blocks it might influence. Values stored in the dictionary are translated to counts in the array result.
Time Complexity: O(k), where k is the number of black cells in 'coordinates'.
Space Complexity: O(b), where b is the number of blocks that contain at least one black cell.
For each 2 times 2 submatrix, we can use its upper-left corner coordinate (x, y) to represent it.
For each black cell (x, y), its contribution to the 4 submatrices is 1, namely the matrices (x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y).
Therefore, we traverse all the black cells, and then accumulate the number of black cells in each submatrix, recorded in the hash table cnt.
Finally, we traverse all the values in cnt (greater than 0), count the number of times they appear, and record them in the answer array ans, while ans[0] represents the number of submatrices without black cells, the value is (m - 1) times (n - 1) - sum_{i = 1}^4 ans[i].
Time complexity O(l), space complexity O(l), where l is the length of coordinates.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(m*n), where m is the number of rows and n is the number of columns in the grid. |
| Efficient Approach Using HashMap | Time Complexity: O(k), where k is the number of black cells in 'coordinates'. |
| Hash Table | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration of 2x2 Blocks | O((m-1)*(n-1)) | O(k) | When grid size is small or for quickly validating logic during interviews |
| HashMap Contribution from Black Cells | O(k) | O(k) | Best general solution when the grid is large but the number of black cells is limited |
2 Approaches | 2768. Number of Black Blocks | Biweekly Contest 108 • codingMohan • 1,554 views views
Watch 8 more video solutions →Practice Number of Black Blocks with our built-in code editor and test cases.
Practice on FleetCode