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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Black Blocks

Difficulty: Medium

Problem Description

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. 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.

Key Insights

  • A block is defined by its top-left corner and consists of four cells.
  • Each 2 x 2 block can be affected by the black cells that are within its boundaries.
  • The maximum number of blocks that can be formed is (m-1) * (n-1).
  • Each black cell can contribute to multiple blocks depending on its position.

Space and Time Complexity

Time Complexity: O(k), where k is the number of black cells in the coordinates array. Space Complexity: O(1), since we only need a fixed-size array to store the result.

Solution

To solve the problem, we can utilize a hash set to keep track of the black cells in the grid. For each black cell, we will update the count of black cells in the blocks it contributes to. Specifically, a black cell at (x, y) influences the blocks starting at (x-1, y-1), (x-1, y), (x, y-1), and (x, y) if those blocks are within bounds. We will then construct the result array by counting how many blocks contain exactly 0, 1, 2, 3, or 4 black cells.

Code Solutions

def countBlackBlocks(m, n, coordinates):
    # Initialize a set to keep track of black cells
    black_cells = set(tuple(coord) for coord in coordinates)
    # Initialize a list to count the number of blocks
    block_count = [0] * 5

    # Iterate through each black cell
    for x, y in black_cells:
        # Check each block that this black cell contributes to
        for dx in range(2):
            for dy in range(2):
                block_x, block_y = x - dx, y - dy
                if 0 <= block_x < m - 1 and 0 <= block_y < n - 1:
                    # Count the number of black cells in the block
                    count = 0
                    for i in range(2):
                        for j in range(2):
                            if (block_x + i, block_y + j) in black_cells:
                                count += 1
                    block_count[count] += 1
                    
    return block_count
← Back to All Questions