Number of Black Blocks

Medium

Capital One

0 views

Topics:

Arrays

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 <= 10⁵
2 <= n <= 10⁵
0 <= coordinates.length <= 10⁴
coordinates[i].length == 2
0 <= coordinates[i][0] < m
0 <= coordinates[i][1] < n
It is guaranteed that coordinates contains pairwise distinct coordinates.

Number of Black Blocks

Medium

Capital One

0 views

Topics:

Arrays

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 <= 10⁵
2 <= n <= 10⁵
0 <= coordinates.length <= 10⁴
coordinates[i].length == 2
0 <= coordinates[i][0] < m
0 <= coordinates[i][1] < n
It is guaranteed that coordinates contains pairwise distinct coordinates.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum value of 'n', the side length of the square grid? What is the maximum number of coordinates that could be in the input list?
Can the coordinates in the input list be outside the bounds of the grid (i.e., x or y < 0 or x or y >= n)?
Are the coordinates guaranteed to be unique, or can there be duplicates in the input list?
If there are no 2x2 blocks containing 'i' points for some 'i', should the corresponding element in the result array be 0?
Is 'n' always greater than or equal to 2, or can it be 0 or 1?

Brute Force Solution

Approach

The brute force approach to count black blocks involves checking every possible square location within the grid. For each square, we determine if it is entirely covered by black blocks. We then count the valid squares to arrive at our answer.

Here's how the algorithm would work step-by-step:

Imagine the grid as a large checkerboard.
Think about each possible spot where a smaller square could fit perfectly on the checkerboard.
Start by focusing on the very first spot in the top-left corner.
Carefully check every single small block inside that spot to see if it's a black block.
If every block inside the spot is black, then we've found a valid location.
If even one block inside the spot is not black, move on.
Now, shift the spot a little to the right and repeat the process, checking all the blocks inside again.
Keep shifting the spot to the right until you reach the end of the checkerboard.
Then, move the spot down a little and start again from the left, checking all the blocks.
Repeat this process until you've checked every possible spot where the smaller square could fit on the large checkerboard.
Finally, count how many times you found a valid spot (a spot where every block inside was black). This count is the answer.

Code Implementation

def count_black_blocks_brute_force(grid, square_size):
    grid_height = len(grid)
    grid_width = len(grid[0])
    valid_square_count = 0

    # Iterate through all possible top-left corners of the square
    for row_start in range(grid_height - square_size + 1):
        for column_start in range(grid_width - square_size + 1):

            is_valid_square = True
            # Check each block within the current square
            for row_index in range(row_start, row_start + square_size):
                for column_index in range(column_start, column_start + square_size):

                    # If any block is not black, the square is invalid
                    if grid[row_index][column_index] == 0:
                        is_valid_square = False
                        break

                if not is_valid_square:
                    break

            # Increment the count if the square is entirely black
            if is_valid_square:
                valid_square_count += 1

    return valid_square_count

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*n*k*k) – Let n be the dimension of the grid and k be the dimension of the square we are searching for. The brute force approach iterates through all possible top-left corners of the square, resulting in (n-k+1)*(n-k+1) possible positions. For each position, we need to check if all k*k blocks within the square are black. Therefore, the overall time complexity is proportional to (n-k+1)*(n-k+1)*k*k. Simplifying this, as n grows much larger than k, we approximate the runtime as n*n*k*k, leading to a time complexity of O(n*n*k*k).

Space Complexity

O(1) – The provided brute force approach iterates through the grid by shifting a 'spot' to check for all black blocks. It doesn't mention storing intermediate results, gathering items, or keeping track of visited locations. The algorithm operates in place by only needing to store a few variables (likely representing the coordinates of the current 'spot'). Therefore, the auxiliary space remains constant regardless of the input size (the grid's dimensions), resulting in O(1) space complexity.

Optimal Solution

Approach

We are given a grid and some points on it. We want to figure out, for each possible square shape in the grid, how many squares contain a certain number of points. The clever bit is to count how many points fall within each square, rather than checking every square individually for each point.

Here's how the algorithm would work step-by-step:

First, go through each point and note its location in the grid.
Then, for each point, imagine it as the bottom right corner of different sized squares.
For each of these squares, count how many other points are also inside that square.
After counting, we will have a list of how many squares have exactly zero points, one point, two points, and three or four points.
Return these counts.

Code Implementation

def number_of_black_blocks(grid_size, points):
    point_set = set()
    for point_x, point_y in points:
        point_set.add((point_x, point_y))

    grid_length = grid_size[0]
    grid_width = grid_size[1]

    counts = [0] * 5

    for point_x, point_y in points:
        for square_size in range(1, min(grid_length - point_x + 2, grid_width - point_y + 2)):
            square_points = 0

            # Count points within current square
            for internal_point_x in range(point_x - square_size + 1, point_x + 1):
                for internal_point_y in range(point_y - square_size + 1, point_y + 1):
                    if (internal_point_x, internal_point_y) in point_set:
                        square_points += 1

            counts[square_points] += 1

    # Initialize result list with counts
    result = []
    for count in counts:
        result.append(count)

    return result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^2) – Let n be the number of points in the grid. The algorithm iterates through each of the n points. For each point, it considers it as the bottom-right corner of squares of varying sizes. In the worst-case, for each point, the algorithm iterates through all other points to determine if they lie within the square formed. This results in a nested loop structure where for each of the n points, we potentially check up to n-1 other points. This leads to approximately n * (n-1) operations which simplifies to O(n^2).

Space Complexity

O(N) – The algorithm stores the locations of all N points in the grid. The counts for the number of squares having zero, one, two, three, and four points are stored. This count array has a fixed size of 5. Therefore, the dominant space complexity is determined by the storage of the N points. Thus, the auxiliary space used is O(N).

Edge Cases

Case	How to Handle
n is less than 2	Return an array of [0, 0, 0, 0, 0] because no 2x2 block can exist if n < 2.
coordinates is null or empty	Return an array of [0, 0, 0, 0, 0] because there are no points to consider for counting 2x2 blocks.
Coordinates contain values outside of the grid (x or y < 0 or x or y >= n)	Filter out coordinates outside the grid's bounds before processing them, to avoid out-of-bounds access.
Large n causing integer overflow when calculating the count of 2x2 blocks.	Use a data type (like long) that can accommodate larger numbers to avoid integer overflow during count calculations.
All coordinates are clustered in one corner of the grid.	The algorithm should correctly count the 2x2 blocks even if the distribution of coordinates is skewed.
Duplicate coordinates in the coordinates array.	Treat duplicate coordinates as if a block contains multiple points at the same location; this does not require special handling if implemented correctly by incrementing a count.
n is very large and most of the grid is empty (sparse grid).	The solution should be efficient enough to handle large grids by only iterating through present coordinates.
Coordinates very close to the boundary of grid.	Ensure the algorithm doesn't try to access out-of-bounds elements when checking for 2x2 squares near the edge.