We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Black Blocks

Number: 2889

Difficulty: Medium

Paid? No

Companies: Uber, Capital One, X, Block

Problem Description

Given an m x n grid, some cells are colored black as specified by the coordinates list. A 2x2 block is defined by its top-left corner. Count and return an array of size 5 where the value at index i indicates the number of 2x2 blocks that contain exactly i black cells.

Key Insights

  • Each black cell can affect up to 4 different 2x2 blocks.
  • Use a hash table/dictionary to record the count of black cells for each block (indexed by the block's top-left coordinate).
  • After updating counts for all blocks influenced by black cells, floor blocks that were never updated have 0 black cells.
  • Compute the total number of blocks as (m-1) * (n-1) and adjust the result accordingly.

Space and Time Complexity

Time Complexity: O(k) where k is the number of black cells, since each cell contributes to at most 4 blocks. Space Complexity: O(k) for storing counts for the blocks that are affected.

Solution

We can solve the problem by iterating over each black cell and updating the count for every possible 2x2 block that the cell belongs to. Specifically, for a black cell at (x, y), the potential block top-left coordinates are (x-1, y-1), (x-1, y), (x, y-1), and (x, y) provided they form valid blocks within the grid boundaries. Store these counts in a hash table (or dictionary). Finally, calculate the number of blocks with 0 black cells by subtracting the blocks that were modified from the total number of blocks ((m-1)*(n-1)). This approach leverages hash table lookups and a simple enumeration of affected blocks.

Code Solutions

# Python solution for "Number of Black Blocks"
class Solution:
    def countBlackBlocks(self, m: int, n: int, coordinates: List[List[int]]) -> List[int]:
        # Dictionary to store the count of black cells for each block.
        block_counts = {}
        
        # Iterate through each black cell coordinate.
        for x, y in coordinates:
            # For each black cell, it can belong to up to 4 blocks.
            for dx in [0, -1]:
                for dy in [0, -1]:
                    block_x = x + dx
                    block_y = y + dy
                    # Check if the block with top-left (block_x, block_y) is valid.
                    if 0 <= block_x < m - 1 and 0 <= block_y < n - 1:
                        block_counts[(block_x, block_y)] = block_counts.get((block_x, block_y), 0) + 1
        
        # Initialize the result array with 5 zeros.
        result = [0] * 5
        
        # Count blocks with 1 to 4 black cells based on our dictionary.
        for count in block_counts.values():
            result[count] += 1

        # Calculate the total number of blocks in the grid.
        total_blocks = (m - 1) * (n - 1)
        # Blocks with 0 black cells are those not present in block_counts.
        result[0] = total_blocks - sum(result[1:])
        return result
← Back to All Questions