Scale Engineer

Number of Black Blocks

Med
#2485Time: O(m * n + C), where C is the number of black cells. `O(C)` to populate the `HashSet` and `O(m * n)` to iterate through all blocks. Given `m, n` up to 10^5, this is too slow.Space: O(C), where C is the number of black cells. This space is used to store the black cell coordinates in the `HashSet`.5 companies
Patterns
Enumeration
Data structures
ArrayHash Table
Companies
VisaCapital OneXSIG

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through every possible 2x2 block in the grid. For each block, we count the number of black cells it contains and update our result array accordingly. This is a straightforward but highly inefficient method given the potential size of the grid.

Algorithm

  • Create a HashSet to store the coordinates of all black cells for quick lookups.
  • Initialize a result array ans of size 5 to all zeros.
  • Iterate through each possible top-left corner (r, c) of a 2x2 block, where 0 <= r < m-1 and 0 <= c < n-1.
  • For each block, count the number of black cells (k) it contains by checking its four cells against the HashSet.
  • If k > 0, increment ans[k].
  • Calculate the total number of blocks: total = (m-1) * (n-1).
  • Calculate the number of blocks with zero black cells: ans[0] = total - (ans[1] + ans[2] + ans[3] + ans[4]).
  • Return the ans array.

Walkthrough

First, we need an efficient way to check if a given cell is black. We can store all the black cell coordinates from the coordinates array into a HashSet for average O(1) lookup time. To store a 2D coordinate [r, c] in the set, we can encode it into a single long value, for instance, (long)r * n + c, to avoid issues with hashing arrays or custom pair objects.

We initialize a result array ans of size 5 with all zeros.

The core of the algorithm is a nested loop that iterates through all possible top-left corners [r, c] of a 2x2 block. The row r goes from 0 to m-2, and the column c goes from 0 to n-2.

Inside the loop, for each block, we check its four cells: [r, c], [r+1, c], [r, c+1], and [r+1, c+1]. We count how many of these are present in our HashSet of black cells.

Let's say we find k black cells in the current block. We then increment ans[k]. Note that we only update counts for blocks with k > 0 to simplify the final calculation for ans[0].

After iterating through all (m-1) * (n-1) blocks, the array ans will contain the counts for blocks with 1, 2, 3, and 4 black cells. The count for blocks with 0 black cells is not yet correct.

The total number of 2x2 blocks is (long)(m-1) * (n-1). The number of blocks with at least one black cell is the sum ans[1] + ans[2] + ans[3] + ans[4]. Therefore, the number of blocks with zero black cells is ans[0] = totalBlocks - (ans[1] + ans[2] + ans[3] + ans[4]).

Finally, we return the ans array.

import java.util.HashSet;import java.util.Set; class Solution {    public long[] countBlackBlocks(int m, int n, int[][] coordinates) {        Set<Long> blackCells = new HashSet<>();        for (int[] coord : coordinates) {            long r = coord[0];            long c = coord[1];            blackCells.add(r * n + c);        }         long[] ans = new long[5];        // This loop is too slow for the given constraints        for (int r = 0; r < m - 1; r++) {            for (int c = 0; c < n - 1; c++) {                int blackCount = 0;                if (blackCells.contains((long)r * n + c)) blackCount++;                if (blackCells.contains((long)(r + 1) * n + c)) blackCount++;                if (blackCells.contains((long)r * n + (c + 1))) blackCount++;                if (blackCells.contains((long)(r + 1) * n + (c + 1))) blackCount++;                                if (blackCount > 0) {                    ans[blackCount]++;                }            }        }         long totalBlocks = (long)(m - 1) * (n - 1);        long nonZeroBlocks = 0;        for (int i = 1; i < 5; i++) {            nonZeroBlocks += ans[i];        }        ans[0] = totalBlocks - nonZeroBlocks;         return ans;    }}

Complexity

Time

O(m * n + C), where C is the number of black cells. `O(C)` to populate the `HashSet` and `O(m * n)` to iterate through all blocks. Given `m, n` up to 10^5, this is too slow.

Space

O(C), where C is the number of black cells. This space is used to store the black cell coordinates in the `HashSet`.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correct for small grids.

Cons

  • Extremely inefficient for large grids.

  • Will result in a "Time Limit Exceeded" error on platforms like LeetCode due to the m * n loop.

Solutions

class Solution {public  long[] countBlackBlocks(int m, int n, int[][] coordinates) {    Map<Long, Integer> cnt = new HashMap<>(coordinates.length);    int[] dirs = {0, 0, -1, -1, 0};    for (var e : coordinates) {      int x = e[0], y = e[1];      for (int k = 0; k < 4; ++k) {        int i = x + dirs[k], j = y + dirs[k + 1];        if (i >= 0 && i < m - 1 && j >= 0 && j < n - 1) {          cnt.merge(1L * i * n + j, 1, Integer : : sum);        }      }    }    long[] ans = new long[5];    ans[0] = (m - 1L) * (n - 1);    for (int x : cnt.values()) {      ++ans[x];      --ans[0];    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem