Number of Black Blocks

Medium
1802.

Number of Black Blocks

Number of Black Blocks is a medium coding problem on arrays, hash table and enumeration, asked in Amazon interviews.

A grid has m rows and n columns. Every cell is white except those listed in coordinates, where coordinates[i] = [x, y] marks cell (x, y) black.

A block is a 2 x 2 sub-grid: the cells (x, y), (x + 1, y), (x, y + 1) and (x + 1, y + 1) for some top-left corner with 0 <= x < m - 1 and 0 <= y < n - 1. There are (m - 1) · (n - 1) blocks in all.

Return an array arr of length 5 where arr[i] is the number of blocks containing exactly i black cells.

CodeKairo bound: m and n are at most 4 · 10^4 here (the original allows 10^5), so the number of all-white blocks always fits in a 32-bit integer.

Example 1

Input
m = 3, n = 3, coordinates = [[0,0]]
Output
[3,1,0,0,0]
Explanation
Only the top-left block contains the black cell.

Example 2

Input
m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
Output
[0,2,2,0,0]
Explanation
The two top blocks hold two black cells each; the two bottom blocks hold just the centre cell.

Example 3

Input
m = 2, n = 2, coordinates = [[0,0],[0,1],[1,0],[1,1]]
Output
[0,0,0,0,1]

Constraints

  • 2 <= m, n <= 4 * 10^4
  • 1 <= coordinates.length <= 10^4
  • coordinates[i].length == 2
  • 0 <= coordinates[i][0] < m
  • 0 <= coordinates[i][1] < n
  • All coordinates are distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} coordinates
 * @return {number[]}
 */
var countBlackBlocks = function(m, n, coordinates) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Black Blocks — Solution in Python, Java & C++

Number of Black Blocks solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon.

Number of Black Blocks is a medium coding problem on arrays, hash table and enumeration, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Enumeration
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A grid has m rows and n columns. Every cell is white except those listed in coordinates, where coordinates[i] = [x, y] marks cell (x, y) black.

A block is a 2 x 2 sub-grid: the cells (x, y), (x + 1, y), (x, y + 1) and (x + 1, y + 1) for some top-left corner with 0 <= x < m - 1 and 0 <= y < n - 1. There are (m - 1) · (n - 1) blocks in all.

Return an array arr of length 5 where arr[i] is the number of blocks containing exactly i black cells.

CodeKairo bound: m and n are at most 4 · 10^4 here (the original allows 10^5), so the number of all-white blocks always fits in a 32-bit integer.

Example 1

Input: m = 3, n = 3, coordinates = [[0,0]]
Output: [3,1,0,0,0]
Explanation: Only the top-left block contains the black cell.

Example 2

Input: m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
Output: [0,2,2,0,0]
Explanation: The two top blocks hold two black cells each; the two bottom blocks hold just the centre cell.

Example 3

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

Constraints

  • 2 <= m, n <= 4 * 10^4
  • 1 <= coordinates.length <= 10^4
  • coordinates[i].length == 2
  • 0 <= coordinates[i][0] < m
  • 0 <= coordinates[i][1] < n
  • All coordinates are distinct

Hints for Number of Black Blocks

  1. Hint 1

    There can be over a billion blocks, so you cannot visit them all — but only blocks that touch a black cell can hold a non-zero count.

  2. Hint 2

    A black cell (x, y) lies in at most four blocks: those with top-left corners (x - 1, y - 1), (x - 1, y), (x, y - 1) and (x, y) that are inside the grid.

  3. Hint 3

    Count, per touched block, how many black cells landed in it (a hash map keyed by the corner). Every block never touched has zero black cells.

How to solve Number of Black Blocks

Instead of looking at blocks, let each black cell vote for the at most four blocks that contain it. A hash map from block corner to vote count then gives every non-empty block's black-cell count directly, and the all-white blocks are whatever is left over.

Approach

  1. For every black cell (x, y) and each corner (bx, by) in {x - 1, x} × {y - 1, y}, if 0 <= bx < m - 1 and 0 <= by < n - 1, increment count[(bx, by)] (encode the corner as bx · n + by).
  2. For every entry of the map, increment arr[count].
  3. Set arr[0] = (m - 1) · (n - 1) − (arr[1] + arr[2] + arr[3] + arr[4]).

Why it works

Block (bx, by) contains cell (x, y) exactly when bx ∈ {x - 1, x} and by ∈ {y - 1, y}, so each black cell increments precisely the blocks that contain it, once each. A block's final value is therefore its number of black cells, and blocks absent from the map have none.

Complexity

  • Time — O(k) expected for k black cells
  • Space — O(k)

Pitfalls

  • Iterating over all (m - 1)(n - 1) blocks times out for large grids.
  • Corners on the last row or column (bx = m - 1 or by = n - 1) are not blocks and must be skipped.
  • (m - 1) · (n - 1) can reach about 1.6 · 10^9 here — compute it in 64-bit where an intermediate could overflow.

Reference solution

Python

from typing import List

def countBlackBlocks(m: int, n: int, coordinates: List[List[int]]) -> List[int]:
    count = {}
    for x, y in coordinates:
        for bx in (x - 1, x):
            if bx < 0 or bx >= m - 1:
                continue
            for by in (y - 1, y):
                if by < 0 or by >= n - 1:
                    continue
                key = bx * n + by
                count[key] = count.get(key, 0) + 1
    arr = [0] * 5
    for c in count.values():
        arr[c] += 1
    arr[0] = (m - 1) * (n - 1) - sum(arr[1:])
    return arr

Java

public static int[] countBlackBlocks(int m, int n, int[][] coordinates) {
    HashMap<Long, Integer> count = new HashMap<>();
    for (int[] c : coordinates) {
        int x = c[0], y = c[1];
        for (int bx = x - 1; bx <= x; bx++) {
            if (bx < 0 || bx >= m - 1) continue;
            for (int by = y - 1; by <= y; by++) {
                if (by < 0 || by >= n - 1) continue;
                count.merge((long) bx * n + by, 1, Integer::sum);
            }
        }
    }
    int[] arr = new int[5];
    for (int v : count.values()) arr[v]++;
    long all = (long) (m - 1) * (n - 1);
    arr[0] = (int) (all - arr[1] - arr[2] - arr[3] - arr[4]);
    return arr;
}

C++

vector<int> countBlackBlocks(int m, int n, vector<vector<int>>& coordinates) {
    unordered_map<long long, int> count;
    for (auto& c : coordinates) {
        int x = c[0], y = c[1];
        for (int bx = x - 1; bx <= x; bx++) {
            if (bx < 0 || bx >= m - 1) continue;
            for (int by = y - 1; by <= y; by++) {
                if (by < 0 || by >= n - 1) continue;
                count[(long long) bx * n + by]++;
            }
        }
    }
    vector<int> arr(5, 0);
    for (auto& kv : count) arr[kv.second]++;
    long long all = (long long) (m - 1) * (n - 1);
    arr[0] = (int) (all - arr[1] - arr[2] - arr[3] - arr[4]);
    return arr;
}

JavaScript

var countBlackBlocks = function(m, n, coordinates) {
    var count = new Map();
    for (var i = 0; i < coordinates.length; i++) {
        var x = coordinates[i][0], y = coordinates[i][1];
        for (var bx = x - 1; bx <= x; bx++) {
            if (bx < 0 || bx >= m - 1) continue;
            for (var by = y - 1; by <= y; by++) {
                if (by < 0 || by >= n - 1) continue;
                var key = bx * n + by;
                var prev = count.get(key);
                count.set(key, (prev === undefined ? 0 : prev) + 1);
            }
        }
    }
    var arr = [0, 0, 0, 0, 0];
    count.forEach(function(c) { arr[c]++; });
    arr[0] = (m - 1) * (n - 1) - arr[1] - arr[2] - arr[3] - arr[4];
    return arr;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets