Number of Black Blocks

Medium Arrays & Hashing Hashing Original on LeetCode

Reported atStripeVisa

Number of Black Blocks is a medium arrays & hashing problem solved with the hashing pattern. The best approach, optimal (count only the blocks touched by black cells), runs in O(k) time and O(k) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (check every block) up.

Problem

You are given an m x n grid whose cells start out white, and a list coordinates where each [x, y] marks the cell in row x, column y as black.

A block is any 2 x 2 square of cells fully inside the grid; a block is identified by its top-left cell (x, y), so it covers (x, y), (x + 1, y), (x, y + 1) and (x + 1, y + 1).

Return an array result of length 5 where result[i] is the number of blocks that contain exactly i black cells.

Examples

Example 1

Input
m = 3, n = 3, coordinates = [[1, 1]]
Output
[0, 4, 0, 0, 0]
Why
The centre cell is shared by all four 2 x 2 blocks of the 3 x 3 grid, so each block holds exactly one black cell.

Example 2

Input
m = 2, n = 4, coordinates = [[0, 0], [1, 1], [0, 3]]
Output
[0, 2, 1, 0, 0]
Why
Blocks start at columns 0, 1 and 2. The first holds (0,0) and (1,1); the second holds only (1,1) and the third only (0,3).

Example 3

Input
m = 4, n = 3, coordinates = []
Output
[6, 0, 0, 0, 0]
Why
There are 3 x 2 = 6 blocks and none of them touches a black cell.

Constraints

  • 2 <= m, n <= 10^5
  • 0 <= coordinates.length <= 10^4
  • coordinates[i] = [x, y] with 0 <= x < m and 0 <= y < n
  • All coordinates are distinct.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (check every block)O(m · n)O(k)
Optimal (count only the blocks touched by black cells)O(k)O(k)

1Brute force (check every block)

TimeO(m · n)Every one of the (m-1)(n-1) blocks is checked with four set lookups.
SpaceO(k)The set holds the k black cells.

Put the black cells in a hash set. Then visit every 2 x 2 block by its top-left corner, look up its four cells in the set and add one to the bucket matching the count.

  1. Store each black cell as the number x * n + y in a hash set.
  2. For every top-left corner (r, c) with r < m - 1 and c < n - 1, count how many of (r, c), (r+1, c), (r, c+1), (r+1, c+1) are in the set.
  3. Increase result[count] by one and return result.
class Solution {
    public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
        Set<Long> black = new HashSet<>();
        for (int[] c : coordinates) black.add((long) c[0] * n + c[1]);
        long[] result = new long[5];
        for (int r = 0; r < m - 1; r++) {
            for (int c = 0; c < n - 1; c++) {
                int cnt = 0;
                for (int dr = 0; dr < 2; dr++) {
                    for (int dc = 0; dc < 2; dc++) {
                        if (black.contains((long) (r + dr) * n + (c + dc))) cnt++;
                    }
                }
                result[cnt]++;
            }
        }
        return result;
    }
}

2Optimal (count only the blocks touched by black cells)

TimeO(k)Each of the k black cells updates at most four map entries.
SpaceO(k)The map holds at most 4k blocks.

Each black cell (x, y) lies in at most four blocks, whose top-left corners are (x-1, y-1), (x-1, y), (x, y-1) and (x, y). Add one to a hash map entry for each of those corners that is a valid block. After all cells, every map value is that block's black count. All remaining blocks are fully white.

  1. For each black cell and each (r, c) in {x-1, x} x {y-1, y}: if 0 <= r < m - 1 and 0 <= c < n - 1, increment map[r * n + c].
  2. For every value v in the map, increment result[v].
  3. Set result[0] = (m - 1) * (n - 1) - map.size() using 64-bit arithmetic.
class Solution {
    public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
        Map<Long, Integer> count = new HashMap<>();
        for (int[] cell : coordinates) {
            int x = cell[0], y = cell[1];
            for (int r = x - 1; r <= x; r++) {
                for (int c = y - 1; c <= y; c++) {
                    if (r >= 0 && r < m - 1 && c >= 0 && c < n - 1) {
                        count.merge((long) r * n + c, 1, Integer::sum);
                    }
                }
            }
        }
        long[] result = new long[5];
        for (int v : count.values()) result[v]++;
        result[0] = (long) (m - 1) * (n - 1) - count.size();
        return result;
    }
}

Edge cases to test

  • No black cells: every block lands in result[0]
  • A 2 x 2 grid fully painted: one block with four black cells
  • Black cells on the border or in a corner belong to fewer blocks (1 or 2 instead of 4)
  • Huge grids (10^5 x 10^5): the number of blocks is about 10^10, so it needs a 64-bit count

Hints

Hint 1

The grid can have about 10^10 blocks, far too many to visit. But only blocks that touch a black cell can have a non-zero count.

Hint 2

Name each block by its top-left cell. A black cell (x, y) belongs to at most four blocks: the ones with top-left (x-1..x, y-1..y), as long as they fit inside the grid.

Hint 3

Count black cells per block in a hash map. Each map value tells you which bucket (1 to 4) that block goes into; every block not in the map holds zero black cells.

FAQ

What is the best time complexity for Number of Black Blocks?

Optimal (count only the blocks touched by black cells) runs in O(k) time and O(k) extra space. Each of the k black cells updates at most four map entries.

Which pattern does Number of Black Blocks use?

It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.

Is there a brute force solution for Number of Black Blocks?

Yes. Brute force (check every block) takes O(m · n) time and O(k) space. Put the black cells in a hash set.

Which edge cases should I test for Number of Black Blocks?

No black cells: every block lands in result[0]; A 2 x 2 grid fully painted: one block with four black cells; Black cells on the border or in a corner belong to fewer blocks (1 or 2 instead of 4); Huge grids (10^5 x 10^5): the number of blocks is about 10^10, so it needs a 64-bit count.