Watch 9 video solutions for Number of Black Blocks, a medium level problem involving Array, Hash Table, Enumeration. This walkthrough by codingMohan has 1,554 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |