Katkat
Back

Find bounding boxes of connected houses

RipplingSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to perform graph traversal (BFS/DFS) on a 2D grid to identify distinct connected components and compute their spatial extent.

Problem: Find House Bounding Boxes

You are given a 2D grid representing a top-down map of a neighborhood. The grid contains two types of cells: 0 representing empty land and 1 representing part of a house. Two house cells are considered part of the same house if they are connected horizontally or vertically (not diagonally).

Your task is to identify every unique house and return the bounding box for each one. A bounding box is defined by the coordinates of its top-left corner (r1, c1) and bottom-right corner (r2, c2).

Function Signature

def find_house_bounding_boxes(grid: List[List[int]]) -> List[List[int]]:

Input

  • grid: A 2D list of integers (0 or 1). The grid may be empty.

Output

  • Return a list of lists, where each inner list contains [r1, c1, r2, c2] representing a house's bounding box. The order of the output list does not matter.

Constraints

  • The grid dimensions are up to 500x500.
  • Time complexity should be O(rows * cols).

Examples

Example 1:

Input:
grid = [
  [1, 1, 0],
  [1, 0, 0],
  [0, 0, 1]
]
Output: [[0, 0, 1, 1], [2, 2, 2, 2]]

Explanation: The house at (0,0), (0,1), and (1,0) forms one component with top-left (0,0) and bottom-right (1,1). The house at (2,2) forms a second component.

Edge Cases

  • Empty grid.
  • Grid with no houses.
  • A grid consisting entirely of houses.
  • Non-rectangular or single-row/column grids.

Hints

Hint 1

Iterate through every cell in the grid, and when you encounter a '1' that has not been visited, you have found a new house.

Hint 2

Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse all cells belonging to the current house, keeping track of the minimum and maximum row and column indices encountered.

Hint 3

Maintain a `visited` set or modify the input grid in-place (if allowed) to ensure each house cell is processed exactly once.

Follow-up questions

  • How would you modify your solution if houses could be connected diagonally?
  • If the grid is extremely large (e.g., millions of cells) and doesn't fit in memory, how would you approach the problem?
  • How would you optimize your search if you only needed to find the bounding box of the largest house by area?