How should I practice Map Black Cells to Covering 2x2 Blocks?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Square phone screen problems in FastPrep.

Is Map Black Cells to Covering 2x2 Blocks associated with Square?

FastPrep tags this as a Square phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Map Black Cells to Covering 2x2 Blocks

Learn this problem

● Easy

SquareFULLTIMEPHONE SCREEN

Problem statement

You are given a grid with rows rows and cols columns, along with the coordinates of every black cell. For each black cell, list every in-bounds 2 x 2 block that contains it.

Rows and columns are zero-indexed. A 2 x 2 block is identified by the coordinate of its top-left cell. The input coordinates are unique but may appear in any order.

Return one flattened record for each black cell. A record has the form [cellRow, cellCol, blockRow1, blockCol1, blockRow2, blockCol2, ...]. Sort the records lexicographically by (cellRow, cellCol). Within each record, sort the covering block coordinates lexicographically by (blockRow, blockCol).

Function

mapBlackCellsToBlocks(rows: int, cols: int, blackCells: List<List<Integer>>) → List<List<Integer>>

Examples

Example 1

rows = 4cols = 5blackCells = [[2,3],[0,0],[1,2]]return = [[0,0,0,0],[1,2,0,1,0,2,1,1,1,2],[2,3,1,2,1,3,2,2,2,3]]

The corner cell (0, 0) belongs only to the block at (0, 0). Each interior black cell belongs to four blocks. The returned records are ordered by black-cell coordinate even though the input is not.

Example 2

rows = 2cols = 4blackCells = [[1,1],[0,3]]return = [[0,3,0,2],[1,1,0,0,0,1]]

Because the grid has exactly two rows, every covering block begins in row 0. The right-corner cell (0, 3) belongs only to block (0, 2), while (1, 1) belongs to blocks (0, 0) and (0, 1).

Example 3

rows = 3cols = 3blackCells = [[1,1]]return = [[1,1,0,0,0,1,1,0,1,1]]

The center cell belongs to all four 2 x 2 blocks, whose top-left coordinates are (0, 0), (0, 1), (1, 0), and (1, 1).

Constraints

2 <= rows, cols <= 10^9
0 <= blackCells.length <= 10^5
blackCells[i].length = 2
0 <= blackCells[i][0] < rows
0 <= blackCells[i][1] < cols
All black-cell coordinates are unique.