Number of Black Blocks - Practice Coding Problems

Number of Black Blocks - Problem

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.

Input & Output

Example 1 — Basic 3x3 Grid

$ Input: m = 3, n = 3, coordinates = [[0,0],[1,1]]

› Output: [1,3,0,0,0]

💡 Note: There are 4 possible 2x2 blocks. Block (0,0) contains cells [(0,0),(0,1),(1,0),(1,1)] with 2 black cells. Block (0,1) contains 1 black cell at (1,1). Block (1,0) contains 1 black cell at (1,1). Block (1,1) contains 0 black cells. So we have 1 block with 0 black, 3 blocks with 1 black, and 0 blocks with 2+ black.

Example 2 — All Black 2x2

$ Input: m = 2, n = 2, coordinates = [[0,0],[0,1],[1,0],[1,1]]

› Output: [0,0,0,0,1]

💡 Note: Only one 2x2 block possible at (0,0) containing all 4 black cells [(0,0),(0,1),(1,0),(1,1)], so result is [0,0,0,0,1].

Example 3 — No Black Cells

$ Input: m = 2, n = 2, coordinates = []

› Output: [1,0,0,0,0]

💡 Note: Only one 2x2 block with no black cells, so result is [1,0,0,0,0].

Constraints

1 ≤ m, n ≤ 10⁵
0 ≤ coordinates.length ≤ 10⁴
coordinates[i].length == 2
0 ≤ x_i < m
0 ≤ y_i < n
It is guaranteed that coordinates contains pairwise distinct coordinates.

Visualization

Tap to expand

Understanding the Visualization

Input Grid

3x3 grid with black cells at (0,0) and (1,1)

Find All Blocks

Identify all possible 2x2 blocks and count black cells

Count by Density

Group blocks by number of black cells: [1,3,0,0,0]

Key Takeaway

🎯 Key Insight: Use hash set for O(1) coordinate lookup when checking each 2x2 block's black cells

Asked in

M Microsoft 25 G Google 20

The key insight is to use a hash set for O(1) coordinate lookups instead of scanning the coordinates array repeatedly. Best approach uses hash map optimization: Time O(m×n + k), Space O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map Optimization	O(m×n + k)	O(k)	Use hash set for O(1) black cell lookups when checking blocks
Brute Force - Check Every Block	O((m×n)×k)	O(1)	Check each 2x2 block by scanning coordinates array for each cell

Hash Map Optimization — Algorithm Steps

Convert coordinates array to hash set for O(1) lookup
Iterate through all possible 2x2 blocks
For each block, count black cells using hash set lookup
Increment appropriate counter based on black cell count

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Hash Set

Convert coordinates to hash set: {(0,0), (1,1)}

Check Blocks

For each block, lookup cells in O(1) time

Count Results

Efficiently count blocks by black cell density

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_COORDS 1000
#define HASH_SIZE 10007

typedef struct Node {
    int x, y;
    struct Node* next;
} Node;

Node* hashTable[HASH_SIZE];

int hash(int x, int y) {
    return (x * 1000 + y) % HASH_SIZE;
}

void insert(int x, int y) {
    int h = hash(x, y);
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->x = x;
    newNode->y = y;
    newNode->next = hashTable[h];
    hashTable[h] = newNode;
}

int contains(int x, int y) {
    int h = hash(x, y);
    Node* curr = hashTable[h];
    while (curr) {
        if (curr->x == x && curr->y == y) return 1;
        curr = curr->next;
    }
    return 0;
}

void solution(int m, int n, int coordinates[][2], int coordSize, int* result) {
    // Initialize hash table
    for (int i = 0; i < HASH_SIZE; i++) {
        hashTable[i] = NULL;
    }
    
    // Insert coordinates into hash table
    for (int i = 0; i < coordSize; i++) {
        insert(coordinates[i][0], coordinates[i][1]);
    }
    
    for (int i = 0; i < 5; i++) result[i] = 0;
    
    // Check each possible 2x2 block
    for (int i = 0; i < m - 1; i++) {
        for (int j = 0; j < n - 1; j++) {
            int blackCount = 0;
            
            // Check all 4 cells in this block
            int blockCells[4][2] = {{i, j}, {i+1, j}, {i, j+1}, {i+1, j+1}};
            
            for (int k = 0; k < 4; k++) {
                if (contains(blockCells[k][0], blockCells[k][1])) {
                    blackCount++;
                }
            }
            
            result[blackCount]++;
        }
    }
}

int main() {
    int m, n;
    scanf("%d", &m);
    scanf("%d", &n);
    
    // Simple parsing for coordinates array
    int coordSize = 0;
    int coordinates[MAX_COORDS][2];
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Parse coordinates from JSON-like format
    char* ptr = line;
    while (*ptr) {
        if (*ptr == '[' && *(ptr+1) != '[') {
            sscanf(ptr, "[%d,%d]", &coordinates[coordSize][0], &coordinates[coordSize][1]);
            coordSize++;
        }
        ptr++;
    }
    
    int result[5];
    solution(m, n, coordinates, coordSize, result);
    
    printf("[");
    for (int i = 0; i < 5; i++) {
        printf("%d", result[i]);
        if (i < 4) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n + k)

Create hash set from k coordinates, then check (m-1)×(n-1) blocks with O(1) lookups

✓ Linear Growth

Space Complexity

O(k)

Hash set stores k coordinate pairs

✓ Linear Space

8.5K Views

Medium Frequency

~15 min Avg. Time

156 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler