2768. Number of Black Blocks LeetCode Solution

In this guide, you will get 2768. Number of Black Blocks LeetCode Solution with the best time and space complexity. The solution to Number of Black Blocks problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Number of Black Blocks solution in C++
Number of Black Blocks solution in Java
Number of Black Blocks solution in Python
Additional Resources

2768. Number of Black Blocks LeetCode Solution image

Problem Statement of Number of Black Blocks

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.

Example 1:

Input: m = 3, n = 3, coordinates = [[0,0]]
Output: [3,1,0,0,0]
Explanation: The grid looks like this:

There is only 1 block with one black cell, and it is the block starting with cell [0,0].
The other 3 blocks start with cells [0,1], [1,0] and [1,1]. They all have zero black cells.
Thus, we return [3,1,0,0,0].

Example 2:

Input: m = 3, n = 3, coordinates = [[0,0],[1,1],[0,2]]
Output: [0,2,2,0,0]
Explanation: The grid looks like this:

There are 2 blocks with two black cells (the ones starting with cell coordinates [0,0] and [0,1]).
The other 2 blocks have starting cell coordinates of [1,0] and [1,1]. They both have 1 black cell.
Therefore, we return [0,2,2,0,0].

Constraints:

2 <= m <= 105
2 <= n <= 105
0 <= coordinates.length <= 104
coordinates[i].length == 2
0 <= coordinates[i][0] < m
0 <= coordinates[i][1] < n
It is guaranteed that coordinates contains pairwise distinct coordinates.

Complexity Analysis

Time Complexity: O(|\texttt{coordinates}|)
Space Complexity: O(|\texttt{coordinates}|)

2768. Number of Black Blocks LeetCode Solution in C++

class Solution {
 public:
  vector<long long> countBlackBlocks(int m, int n,
                                     vector<vector<int>>& coordinates) {
    vector<long long> ans(5);
    // count[i * n + j] := the number of black cells in
    // (i - 1, j - 1), (i - 1, j), (i, j - 1), (i, j)
    unordered_map<long, int> count;

    for (const vector<int>& coordinate : coordinates) {
      const int x = coordinate[0];
      const int y = coordinate[1];
      for (long i = x; i < x + 2; ++i)
        for (long j = y; j < y + 2; ++j)
          // 2 x 2 submatrix with right-bottom conner being (i, j) contains the
          // current black cell (x, y).
          if (i - 1 >= 0 && i < m && j - 1 >= 0 && j < n)
            ++count[i * n + j];
    }

    for (const auto& [_, freq] : count)
      ++ans[freq];

    ans[0] = (m - 1L) * (n - 1) - accumulate(ans.begin(), ans.end(), 0L);
    return ans;
  }
};
/* code provided by PROGIEZ */

2768. Number of Black Blocks LeetCode Solution in Java

class Solution {
  public long[] countBlackBlocks(int m, int n, int[][] coordinates) {
    long[] ans = new long[5];
    // count[i * n + j] := the number of black cells in
    // (i - 1, j - 1), (i - 1, j), (i, j - 1), (i, j)
    Map<Long, Integer> count = new HashMap<>();

    for (int[] coordinate : coordinates) {
      final int x = coordinate[0];
      final int y = coordinate[1];
      for (long i = x; i < x + 2; ++i)
        for (long j = y; j < y + 2; ++j)
          // 2 x 2 submatrix with right-bottom conner being (i, j) contains the
          // current black cell (x, y).
          if (i - 1 >= 0 && i < m && j - 1 >= 0 && j < n)
            count.merge(i * n + j, 1, Integer::sum);
    }

    for (final int freq : count.values())
      ++ans[freq];

    ans[0] = (m - 1L) * (n - 1) - Arrays.stream(ans).sum();
    return ans;
  }
}
// code provided by PROGIEZ

2768. Number of Black Blocks LeetCode Solution in Python

class Solution:
  def countBlackBlocks(
      self,
      m: int,
      n: int,
      coordinates: list[list[int]],
  ) -> list[int]:
    ans = [0] * 5
    # count[i * n + j] := the number of black cells in
    # (i - 1, j - 1), (i - 1, j), (i, j - 1), (i, j)
    count = collections.Counter()

    for x, y in coordinates:
      for i in range(x, x + 2):
        for j in range(y, y + 2):
          # 2 x 2 submatrix with right-bottom conner being (i, j) contains the
          # current black cell (x, y).
          if 0 < i < m and 0 < j < n:
            count[(i, j)] += 1

    for freq in count.values():
      ans[freq] += 1

    ans[0] = (m - 1) * (n - 1) - sum(ans)
    return ans
 # code by PROGIEZ