Number of black blocks

Array Hash Table Enumeration

41.5% acceptance

Feb 25, 2026

282

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_black_blocks(m: i32, n: i32, coordinates: Vec<Vec<i32>>) -> Vec<i64> {
    use std::collections::HashMap;
    let mut block_count: HashMap<(i64, i64), i64> = HashMap::new();
    for coord in &coordinates {
      let (x, y) = (coord[0] as i64, coord[1] as i64);
      for (dx, dy) in [(-1i64, -1i64), (-1, 0), (0, -1), (0, 0)] {
        let bx = x + dx;
        let by = y + dy;
        if bx >= 0 && by >= 0 && bx < m as i64 - 1 && by < n as i64 - 1 {
          *block_count.entry((bx, by)).or_insert(0) += 1;
        }
      }
    }
    let total_blocks = (m as i64 - 1) * (n as i64 - 1);
    let mut arr = vec![0i64; 5];
    for &cnt in block_count.values() {
      arr[cnt as usize] += 1;
    }
    arr[0] = total_blocks - arr[1] - arr[2] - arr[3] - arr[4];
    arr
  }
}