FastPrep
Problem · Array

Count 2x2 Submatrices by Black Cells

Learn this problem
● MediumHudson River Trading logoHudson River TradingINTERNNEW GRADOA

Problem statement

You are given a black-and-white grid with rows rows and cols columns. The array black contains the [row, column] coordinates of every black cell in the grid. All other cells are white, and the black-cell coordinates are pairwise unique.

For every blackCount from 0 through 4, count how many 2 x 2 submatrices contain exactly blackCount black cells.

Return an array result of length 5, where result[i] is the number of 2 x 2 submatrices containing exactly i black cells.

Function

solution(rows: int, cols: int, black: int[][]) → long[]

Examples

Example 1

rows = 3cols = 3black = [[0, 0], [0, 1], [1, 0]]return = [1, 2, 0, 1, 0]

There are four 2 x 2 submatrices:

  • The submatrix with upper-left corner (0, 0) contains 3 black cells.
  • The submatrix with upper-left corner (0, 1) contains 1 black cell.
  • The submatrix with upper-left corner (1, 0) contains 1 black cell.
  • The submatrix with upper-left corner (1, 1) contains 0 black cells.

Therefore, the counts for 0 through 4 black cells are [1, 2, 0, 1, 0].

Constraints

  • 2 <= rows <= 10^5
  • 2 <= cols <= 10^5
  • 0 <= black.length <= 500
  • black[i].length = 2
  • 0 <= black[i][0] < rows
  • 0 <= black[i][1] < cols
  • All coordinates in black are pairwise unique.

More Hudson River Trading problems

drafts saved locally
public long[] solution(int rows, int cols, int[][] black) {
    // write your code here
}
rows3
cols3
black[[0, 0], [0, 1], [1, 0]]
expected[1, 2, 0, 1, 0]
checking account