Number of Black Blocks
MedPrompt
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] < n- It is guaranteed that
coordinatescontains pairwise distinct coordinates.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through every possible 2x2 block in the grid. For each block, we count the number of black cells it contains and update our result array accordingly. This is a straightforward but highly inefficient method given the potential size of the grid.
Algorithm
- Create a
HashSetto store the coordinates of all black cells for quick lookups. - Initialize a result array
ansof size 5 to all zeros. - Iterate through each possible top-left corner
(r, c)of a 2x2 block, where0 <= r < m-1and0 <= c < n-1. - For each block, count the number of black cells (
k) it contains by checking its four cells against theHashSet. - If
k > 0, incrementans[k]. - Calculate the total number of blocks:
total = (m-1) * (n-1). - Calculate the number of blocks with zero black cells:
ans[0] = total - (ans[1] + ans[2] + ans[3] + ans[4]). - Return the
ansarray.
Walkthrough
First, we need an efficient way to check if a given cell is black. We can store all the black cell coordinates from the coordinates array into a HashSet for average O(1) lookup time. To store a 2D coordinate [r, c] in the set, we can encode it into a single long value, for instance, (long)r * n + c, to avoid issues with hashing arrays or custom pair objects.
We initialize a result array ans of size 5 with all zeros.
The core of the algorithm is a nested loop that iterates through all possible top-left corners [r, c] of a 2x2 block. The row r goes from 0 to m-2, and the column c goes from 0 to n-2.
Inside the loop, for each block, we check its four cells: [r, c], [r+1, c], [r, c+1], and [r+1, c+1]. We count how many of these are present in our HashSet of black cells.
Let's say we find k black cells in the current block. We then increment ans[k]. Note that we only update counts for blocks with k > 0 to simplify the final calculation for ans[0].
After iterating through all (m-1) * (n-1) blocks, the array ans will contain the counts for blocks with 1, 2, 3, and 4 black cells. The count for blocks with 0 black cells is not yet correct.
The total number of 2x2 blocks is (long)(m-1) * (n-1). The number of blocks with at least one black cell is the sum ans[1] + ans[2] + ans[3] + ans[4]. Therefore, the number of blocks with zero black cells is ans[0] = totalBlocks - (ans[1] + ans[2] + ans[3] + ans[4]).
Finally, we return the ans array.
import java.util.HashSet;import java.util.Set; class Solution { public long[] countBlackBlocks(int m, int n, int[][] coordinates) { Set<Long> blackCells = new HashSet<>(); for (int[] coord : coordinates) { long r = coord[0]; long c = coord[1]; blackCells.add(r * n + c); } long[] ans = new long[5]; // This loop is too slow for the given constraints for (int r = 0; r < m - 1; r++) { for (int c = 0; c < n - 1; c++) { int blackCount = 0; if (blackCells.contains((long)r * n + c)) blackCount++; if (blackCells.contains((long)(r + 1) * n + c)) blackCount++; if (blackCells.contains((long)r * n + (c + 1))) blackCount++; if (blackCells.contains((long)(r + 1) * n + (c + 1))) blackCount++; if (blackCount > 0) { ans[blackCount]++; } } } long totalBlocks = (long)(m - 1) * (n - 1); long nonZeroBlocks = 0; for (int i = 1; i < 5; i++) { nonZeroBlocks += ans[i]; } ans[0] = totalBlocks - nonZeroBlocks; return ans; }}Complexity
Time
O(m * n + C), where C is the number of black cells. `O(C)` to populate the `HashSet` and `O(m * n)` to iterate through all blocks. Given `m, n` up to 10^5, this is too slow.
Space
O(C), where C is the number of black cells. This space is used to store the black cell coordinates in the `HashSet`.
Trade-offs
Pros
Simple to understand and implement.
Correct for small grids.
Cons
Extremely inefficient for large grids.
Will result in a "Time Limit Exceeded" error on platforms like LeetCode due to the
m * nloop.
This efficient approach avoids iterating through the entire grid. Instead, it focuses only on the black cells. The key insight is that a single black cell can only affect a maximum of four 2x2 blocks. By iterating through each black cell and updating a count for the blocks it influences, we can solve the problem in time proportional to the number of black cells, not the grid size.
Algorithm
- Initialize a
HashMap<Long, Integer>calledblockCountsto store the number of black cells for each affected block. - Iterate through each black cell
(r, c)in thecoordinatesarray. - For each black cell, consider the four potential 2x2 blocks it can belong to (those with top-left corners at
(r, c),(r, c-1),(r-1, c), and(r-1, c-1)). - For each of these four potential blocks, if its top-left corner
(tr, tc)is valid (0 <= tr < m-1and0 <= tc < n-1), increment its count in theblockCountsmap. - After iterating through all black cells, initialize a result array
ansof size 5. - Iterate through the values in
blockCounts. For each valuek, incrementans[k]. - Calculate the total number of blocks:
total = (long)(m - 1) * (n - 1). - The number of blocks with at least one black cell is
blockCounts.size(). - Calculate the number of blocks with zero black cells:
ans[0] = total - blockCounts.size(). - Return the
ansarray.
Walkthrough
The main idea is to count the number of black cells for every block that contains at least one black cell. Blocks with zero black cells can be calculated at the end.
We use a HashMap where the key represents a 2x2 block and the value stores the number of black cells in it. A block is uniquely identified by its top-left corner (r, c). We can encode this 2D coordinate into a single long value (e.g., (long)r * n + c) to use as the map key.
We iterate through each black cell (r, c) from the coordinates input.
For each black cell (r, c), it can be part of four potential 2x2 blocks. These blocks would have their top-left corners at:
(r, c)(r, c-1)(r-1, c)(r-1, c-1)
For each of these four potential top-left corners (tr, tc), we first check if it's a valid corner for a block within the grid (i.e., 0 <= tr < m-1 and 0 <= tc < n-1).
If (tr, tc) is a valid top-left corner, it means the block starting there is affected by the current black cell. We increment the black cell count for this block in our HashMap. We use map.getOrDefault(key, 0) + 1 to handle both existing and new entries.
After processing all black cells, the HashMap will contain every block that has one or more black cells, mapped to its respective black cell count.
We then initialize our result array ans of size 5. We iterate through the values of the HashMap. For each count k, we increment ans[k].
The total number of 2x2 blocks in the grid is (long)(m - 1) * (n - 1). The number of blocks with at least one black cell is simply the size of our HashMap.
The number of blocks with zero black cells is the total number of blocks minus the number of blocks with at least one black cell. So, ans[0] = totalBlocks - map.size().
Finally, we return the ans array.
import java.util.HashMap;import java.util.Map; class Solution { public long[] countBlackBlocks(int m, int n, int[][] coordinates) { Map<Long, Integer> blockCounts = new HashMap<>(); for (int[] coord : coordinates) { int r = coord[0]; int c = coord[1]; // A black cell at (r, c) can affect up to 4 blocks. // We check the 2x2 area around the black cell. // The top-left corners of these potential blocks are: // (r-1, c-1), (r-1, c), (r, c-1), (r, c) for (int i = r - 1; i <= r; i++) { for (int j = c - 1; j <= c; j++) { // Check if (i, j) is a valid top-left corner of a 2x2 block if (i >= 0 && i < m - 1 && j >= 0 && j < n - 1) { long blockId = (long)i * n + j; blockCounts.put(blockId, blockCounts.getOrDefault(blockId, 0) + 1); } } } } long[] ans = new long[5]; long nonZeroBlocks = blockCounts.size(); for (int count : blockCounts.values()) { if (count > 0 && count <= 4) { ans[count]++; } } long totalBlocks = (long)(m - 1) * (n - 1); ans[0] = totalBlocks - nonZeroBlocks; return ans; }}Complexity
Time
O(C), where C is the number of black cells (`coordinates.length`). For each of the `C` cells, we perform a constant number of operations (4 lookups/updates in the HashMap). Iterating through the map at the end takes `O(K)` time, where `K` is the number of affected blocks (`K <= 4*C`). Thus, the total time complexity is linear with respect to the number of black cells.
Space
O(C), where C is the number of black cells (`coordinates.length`). The `HashMap` can store up to `4*C` entries in the worst case, where each black cell affects four distinct blocks. Therefore, the space required is proportional to the number of black cells.
Trade-offs
Pros
Highly efficient, with performance depending on the number of black cells, not the grid size.
Handles the large constraints on
mandneffectively.Optimal solution for this problem.
Cons
Slightly more complex to conceptualize than the brute-force approach.
Requires careful handling of coordinates and boundary checks.
Solutions
Solution
class Solution {public long[] countBlackBlocks(int m, int n, int[][] coordinates) { Map<Long, Integer> cnt = new HashMap<>(coordinates.length); int[] dirs = {0, 0, -1, -1, 0}; for (var e : coordinates) { int x = e[0], y = e[1]; for (int k = 0; k < 4; ++k) { int i = x + dirs[k], j = y + dirs[k + 1]; if (i >= 0 && i < m - 1 && j >= 0 && j < n - 1) { cnt.merge(1L * i * n + j, 1, Integer : : sum); } } } long[] ans = new long[5]; ans[0] = (m - 1L) * (n - 1); for (int x : cnt.values()) { ++ans[x]; --ans[0]; } return ans; }}class Solution {public: vector<long long> countBlackBlocks(int m, int n, vector<vector<int>> &coordinates) { unordered_map<long long, int> cnt; int dirs[5] = {0, 0, -1, -1, 0}; for (auto &e : coordinates) { int x = e[0], y = e[1]; for (int k = 0; k < 4; ++k) { int i = x + dirs[k], j = y + dirs[k + 1]; if (i >= 0 && i < m - 1 && j >= 0 && j < n - 1) { ++cnt[1LL * i * n + j]; } } } vector<long long> ans(5); ans[0] = (m - 1LL) * (n - 1); for (auto &[_, x] : cnt) { ++ans[x]; --ans[0]; } return ans; }};class Solution: def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]: cnt = Counter() for x, y in coordinates: for a, b in pairwise((0, 0, - 1, - 1, 0)): i, j = x + a, y + b if 0 <= i < m - 1 and 0 <= j < n - 1: cnt[(i, j)] += 1 ans = [0] * 5 for x in cnt . values(): ans[x] += 1 ans[0] = (m - 1) * (n - 1) - len(cnt . values()) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.