Show problems as
Classic problem #2768MediumArrayHash TableEnumeration

Number of Black Blocks

Real-world version: Marked Cells in Every Two-by-Two Window
Tracked in this browser only
Read Number of Black Blocks on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A sheet has m rows and n columns of cells, numbered from zero. The cells listed in coordinates, each [row, column], are marked; the rest are blank, and no cell is listed twice.

A window is any two-by-two square of neighbouring cells, so there are (m - 1) * (n - 1) of them.

Return a list of five counts: how many windows hold exactly 0 marked cells, then exactly 1, and so on up to exactly 4.

Examples

Example 1

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

The sheet is a single window and all four of its cells are marked.

Example 2

Input
m = 3, n = 3, coordinates = [[1, 1]]
Output
[0, 4, 0, 0, 0]

The middle cell of a three by three sheet sits in all four windows, so each of them holds exactly one marked cell.

Example 3

Input
m = 100000, n = 100000, coordinates = []
Output
[9999800001, 0, 0, 0, 0]

Nothing is marked, so every one of the windows holds nothing.

Constraints

  • 2 <= m <= 10^5
  • 2 <= n <= 10^5
  • 0 <= coordinates.length <= 10^4
  • coordinates[i].length == 2
  • 0 <= coordinates[i][0] <= m - 1
  • 0 <= coordinates[i][1] <= n - 1
  • No cell is listed twice

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_black_blocks(m: int, n: int, coordinates: list[list[int]]) -> list[int]:
Java
public long[] countBlackBlocks(int m, int n, int[][] coordinates)

More on the same topics