Katkat
Back

List the Two-by-Two Blocks Covering Each Black Cell

SquareSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to navigate grid coordinates, implement range boundaries, and perform efficient dictionary-based data collection.

Problem Statement

You are given a sparse grid represented by a list of (r, c) coordinates, where each coordinate marks the position of a 'black cell'. A 2x2 block is defined by its top-left corner coordinate (r, c). A 2x2 block covers a black cell if the black cell is located at (r, c), (r+1, c), (r, c+1), or (r+1, c+1).

Given a list of black cell coordinates, return a dictionary where each key is a black cell coordinate (r, c) and the value is a list of top-left coordinates (tr, tc) of all possible 2x2 blocks that cover it.

Rules:

  1. A 2x2 block is only valid if all its cells are within a grid of size R x C (i.e., 0 <= tr < R-1 and 0 <= tc < C-1).
  2. For each black cell, sort the resulting list of 2x2 block coordinates in lexicographical order.

Function Signature

def get_covering_blocks(black_cells, R, C):

Example

Input: black_cells = [(0, 0)], R = 3, C = 3 Output: {(0, 0): [(0, 0)]} Explanation: The cell at (0,0) is covered by the block starting at (0,0).

Input: black_cells = [(1, 1)], R = 3, C = 3 Output: {(1, 1): [(0, 0), (0, 1), (1, 0), (1, 1)]} Explanation: The cell at (1,1) is the bottom-right, top-right, bottom-left, and top-left corner of four different 2x2 blocks.

Hints

Hint 1

For any given black cell (r, c), consider the four potential top-left corners of a 2x2 block that could contain it: (r-1, c-1), (r-1, c), (r, c-1), and (r, c).

Hint 2

Iterate through each black cell and check if these four potential top-left corners fall within the bounds of [0, R-2] and [0, C-2].

Hint 3

Use a dictionary to store the results, ensuring that you only include coordinates that satisfy the boundary conditions.

Follow-up questions

  • How would your approach change if the grid size R and C were effectively infinite?
  • What is the time complexity of your solution in terms of the number of black cells N and the grid dimensions?
  • If we wanted to find all black cells covered by a specific 2x2 block, how would you invert the data structure to perform this efficiently?