2768. Number of Black Blocks
Problem Description
In the given problem, we are tasked with assessing a grid with dimensions m x n that is partially colored with black cells at specific coordinates. Initially, we assume that the entire grid is white. A matrix called coordinates is provided to us, where each element [x, y] of this matrix represents a cell in our grid that is black.
What we are interested in is identifying the number of 'blocks' within this grid containing a certain number of black cells. A 'block' is defined as a 2 x 2 section of the grid and may therefore contain between zero and four black cells. In essence, our goal is to count the number of these blocks based on the number of black cells they have, ranging from zero to four.
We are expected to return an array of size five, arr, where arr[i] corresponds to the number of blocks containing exactly i black cells. To put this into perspective, arr[0] will represent the number of blocks with no black cells, and it progresses all the way to arr[4], which represents the number of blocks completely filled with black cells.
Intuition
The intuition behind the solution involves two primary steps: identifying relevant blocks and counting the number of black cells within each block.
Given that a block is defined by its top-left cell, we can consider each black cell's contribution to possibly four different blocks - the ones that could contain this black cell either in their top-left, top-right, bottom-left, or bottom-right position.
To achieve this, we create a hash table (or a dictionary in Python) where the keys correspond to the top-left coordinates of all potential blocks, and the values represent the number of black cells within each block.
As we iterate through each black cell given in the coordinates, we increment the count for the blocks it is part of. We do this carefully, taking into account the edge cases: a black cell that lies on the bottom or right edge of the grid won't be the top-left cell of any block.
The answer to our problem is partially embedded in the hash table - it tells us how many blocks have one or more black cells. However, we still need to account for the blocks that have no black cells at all. To calculate this, we subtract the total number of blocks with at least one black cell (which is just the number of keys in our hash table) from the total number of possible blocks, (m - 1) * (n - 1).
At the end, the ans array is assembled by iterating through the hash table's values and incrementing the count in the array based on the number of black cells in each block.
How many times is a tree node visited in a depth first search?
Solution Approach
The solution employs a hash table to track the number of black cells within each potential block. A hash table is a data structure that allows us to store key-value pairs, where the key is unique. In this case, the keys are tuples representing the top-left corner of each block (x, y), and the values are counts of how many black cells are contained within that block.
We iterate over each black cell given in the coordinates. For each cell (x, y), we consider its contribution to the surrounding blocks. The surrounding blocks that the cell contributes to are identified by shifting the cell's position one step up/to the left ((x - 1, y - 1), (x - 1, y), (x, y - 1), (x, y)). When the cell is on the edge of the grid, some of these shifts would result in invalid coordinates for a block's top-left corner, so we verify that each corner coordinate is valid by checking the grid's bounds.
The Python Counter class is utilized to implement the hash table, which already provides a convenient way to increment the count for each key. As we visit each black cell, we update the counts accordingly.
After accounting for all black cells and their contributions, we are left with a hash table where the keys are the possible upper-left corners of 2 x 2 blocks, and the values are the number of black cells in those blocks. We construct the ans array from this data, where for each key in the hash table, the value associated with it tells us how many black cells that block contains. We increment the corresponding index in ans for the count of such blocks.
Lastly, to calculate the number of blocks that contain zero black cells, we use the formula (m - 1) * (n - 1) - sum(cnt.values()). This takes the total possible number of blocks in our grid, subtracts the number of non-zero entries from our hash table, and gives us the number of white blocks.
By iterating through the values of our hash table and assembling the ans array, we complete the solution and return it as our answer, adhering to the problem's constraints and expectations.
Which of these pictures shows the visit order of a depth-first search?
Example Walkthrough
Let's walk through a small example using the solution approach described above.
Example Grid (m x n): 3 x 3 grid where m and n are the dimensions of the grid
Coordinates of Black Cells: [[1, 1], [1, 2], [2, 1]]
Our grid looks like this initially, where 0 represents white cells:
10 0 0 20 0 0 30 0 0
After coloring the cells from the coordinates, our grid looks like this (1 represents black cells):
10 0 0 20 1 1 30 1 0
Let's identify potential blocks. A 2 x 2 block is defined by its top-left corner. In a 3 x 3 grid, the potential top-left corners are (0, 0), (0, 1), (1, 0), and (1, 1).
Now we iterate over each black cell and update the count for each potential block it is part of. We only increment the count if the coordinate is a valid top-left corner of a block.
For black cell (1, 1):
- It will contribute to blocks with top-left corners at (1, 1), (1, 0), (0, 1), and (0, 0). However, only (1, 1) and (0, 1) are valid blocks since (1, 0) and (0, 0) do not form a complete
2 x 2block within the grid.
For black cell (1, 2):
- It contributes to blocks with top-left corners at (1, 2), (1, 1), (0, 2), and (0, 1). Only (1, 1) and (0, 1) are valid.
For black cell (2, 1):
- It contributes to blocks with top-left corners at (2, 1), (2, 0), (1, 1), and (1, 0). Only (1, 1) is a valid top-left corner for a block.
At this point, the hash table (or Counter) will contain:
- (0, 1): 1 black cell
- (1, 1): 3 black cells
We have only two non-empty blocks; the rest ((m - 1) * (n - 1) = 4) are empty blocks.
To calculate the final array, arr, we do the following:
arr[0]: Number of white blocks ((m - 1) * (n - 1)- number of non-empty blocks) = 4 - 2 = 2.arr[1]: The number of blocks with exactly 1 black cell = 1 (block with the top-left corner at (0, 1)).arr[2]: The number of blocks with exactly 2 black cells = 0.arr[3]: The number of blocks with exactly 3 black cells = 1 (block with the top-left corner at (1, 1)).arr[4]: The number of blocks with exactly 4 black cells = 0.
Therefore, the final returned array will be: arr = [2, 1, 0, 1, 0]. This means there are 2 blocks with 0 black cells, 1 block with 1 black cell, 0 blocks with 2 black cells, 1 block with 3 black cells, and 0 blocks with 4 black cells.
Solution Implementation
1from collections import Counter
2from itertools import pairwise
3
4class Solution:
5 def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:
6 # Counter to keep track of the number of occurrences for each block
7 block_counter = Counter()
8
9 # Iterate through each coordinate
10 for x, y in coordinates:
11 # Generate 4 adjacent positions using pairwise
12 for delta_x, delta_y in pairwise([0, 0, -1, -1, 0]):
13 # New coordinates for the adjacent position
14 i, j = x + delta_x, y + delta_y
15
16 # Check if the new coordinates are inside the grid boundaries
17 if 0 <= i < m - 1 and 0 <= j < n - 1:
18 # Increment the count for this block
19 block_counter[(i, j)] += 1
20
21 # List to store the result; there can be 0 to 4, total 5 different counts
22 result_counts = [0] * 5
23
24 # Update the result list with the counts from the counter
25 for count in block_counter.values():
26 result_counts[count] += 1
27
28 # Calculate the number of blocks with 0 count (not modified by any operation)
29 result_counts[0] = (m - 1) * (n - 1) - sum(block_counter.values())
30
31 return result_counts
321class Solution {
2 public long[] countBlackBlocks(int rows, int cols, int[][] coordinates) {
3 // A map to keep count of shared corners for each black block
4 Map<Long, Integer> sharedCornersCount = new HashMap<>(coordinates.length);
5 // Array to navigate through the neighboring blocks
6 int[] directions = {0, 0, -1, -1, 0};
7
8 // Iterate through the coordinates of the black blocks
9 for (int[] coordinate : coordinates) {
10 int x = coordinate[0], y = coordinate[1];
11 // Consider the neighboring cells, as they share corners with the current cell
12 for (int k = 0; k < 4; k++) {
13 int i = x + directions[k], j = y + directions[k + 1];
14 // Check if the neighboring cell is within the boundaries of the grid
15 if (i >= 0 && i < rows - 1 && j >= 0 && j < cols - 1) {
16 // Using long to avoid integer overflow for indexing
17 long index = 1L * i * cols + j;
18 // Count the shared corners for each cell
19 sharedCornersCount.merge(index, 1, Integer::sum);
20 }
21 }
22 }
23
24 // Array to hold the count of cells with a specific number of shared corners
25 long[] result = new long[5];
26 // By default, all the cells are initialized with no shared corners
27 result[0] = (long)(rows - 1) * (cols - 1);
28 // Iterate through the counts and update the result array accordingly
29 for (int count : sharedCornersCount.values()) {
30 result[count]++; // Increment the count for the specific shared corners
31 result[0]--; // Decrement the count of cells with no shared corners
32 }
33
34 return result;
35 }
36}
371#include <vector>
2#include <unordered_map>
3
4class Solution {
5public:
6 std::vector<long long> countBlackBlocks(int m, int n, std::vector<std::vector<int>>& coordinates) {
7 // A map to keep count of the black blocks shaded by each coordinate
8 std::unordered_map<long long, int> block_counts;
9
10 // Directions representing the relative positions of the 4 neighboring blocks
11 int directions[5] = {0, 0, -1, -1, 0};
12
13 // Loop through each coordinate in the coordinates list
14 for (const auto& coordinate : coordinates) {
15 int x = coordinate[0], y = coordinate[1];
16 // Check all four neighboring positions
17 for (int k = 0; k < 4; ++k) {
18 int neighbor_x = x + directions[k], neighbor_y = y + directions[k + 1];
19 // Check if the neighbor block is within bounds
20 if (neighbor_x >= 0 && neighbor_x < m - 1 && neighbor_y >= 0 && neighbor_y < n - 1) {
21 // Increment the count for the neighbor block key in the map
22 ++block_counts[static_cast<long long>(neighbor_x) * n + neighbor_y];
23 }
24 }
25 }
26
27 // Answer vector containing counts of black blocks shaded 0 to 4 times
28 std::vector<long long> answer(5);
29 // Initially set the count of blocks not shaded to the total number of possible blocks
30 answer[0] = static_cast<long long>(m - 1) * (n - 1);
31 // Update the answer vector based on the counts in the map
32 for (const auto& count : block_counts) {
33 // Increment the count for the number of times a block is shaded
34 ++answer[count.second];
35 // Decrement the count of blocks not shaded
36 --answer[0];
37 }
38
39 // Return the final answer vector
40 return answer;
41 }
42};
431function countBlackBlocks(m: number, n: number, coordinates: number[][]): number[] {
2 // Map to keep track of the count of blocks at each grid position
3 const blockCount: Map<number, number> = new Map();
4 // Directions to move to adjacent cells (left, right, up, down)
5 const directions: number[] = [0, 0, -1, -1, 0];
6
7 // Iterate over each coordinate
8 for (const [row, col] of coordinates) {
9 // Check each direction from the coordinate
10 for (let k = 0; k < 4; ++k) {
11 // Calculate the adjacent cell's position
12 const [adjRow, adjCol] = [row + directions[k], col + directions[k + 1]];
13 // Ensure that the adjacent cell is within the grid bounds
14 if (adjRow >= 0 && adjRow < m - 1 && adjCol >= 0 && adjCol < n - 1) {
15 // Calculate a unique key for the position in the grid
16 const key = adjRow * n + adjCol;
17 // Increment the block count for this key, or set to 1 if it doesn't exist
18 blockCount.set(key, (blockCount.get(key) || 0) + 1);
19 }
20 }
21 }
22
23 // Array to store the final count of black blocks for each count type (0 to 4)
24 const answer: number[] = Array(5).fill(0);
25 // Initialize the answer for count type 0 to the total possible number of grid cells
26 answer[0] = (m - 1) * (n - 1);
27
28 // Iterate over the block count map to populate the answer array
29 for (const count of blockCount.values()) {
30 // Increment the answer for the corresponding count type
31 ++answer[count];
32 // Decrement the answer for count type 0 since we've found a cell with >0 blocks
33 --answer[0];
34 }
35 return answer;
36}
37The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Time and Space Complexity
Time Complexity
The time complexity of the code is primarily dominated by the for loop that iterates through each of the coordinates. Within this loop, there's a call to pairwise, which will have a constant number of iterations (specifically, 2 in this case) since it is paired with a fixed size tuple. Therefore, the complexity due to pairwise does not depend on the size of the input.
Next, we have a nested for loop, but since it also iterates over a fixed-size tuple (four elements), it runs in constant time per coordinate.
Given that each iteration of the main for loop is constant time and we have l coordinates, the overall time complexity is O(l).
Space Complexity
The space complexity is influenced by the Counter object cnt that collects the frequency of each black block. In the worst-case scenario, each coordinate touches a unique block, thus the space required to store counts can grow linearly with the number of coordinates. Therefore, the space complexity is also O(l), where l is the length of coordinates.
Note that the output array ans has a fixed size of 5, and the fixed tuples used for iteration do not scale with input size, so they do not affect the space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.