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^41 <= coordinates.length <= 10^4coordinates[i].length == 20 <= coordinates[i][0] < m0 <= coordinates[i][1] < nAll coordinates are distinct
Hints for Number of Black Blocks
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.
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.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
- For every black cell
(x, y)and each corner(bx, by)in{x - 1, x} × {y - 1, y}, if0 <= bx < m - 1and0 <= by < n - 1, incrementcount[(bx, by)](encode the corner asbx · n + by). - For every entry of the map, increment
arr[count]. - 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 - 1orby = 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 arrJava
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