Katkat
Back

Measure Every Lake on a Map Tile, Listed in Scan Order

MicrosoftSoftware Engineer · Onsite
EasySoftware EngineerOnsiteCoding & Algorithms

Last updated

Compute the area of every water body on a rectangular map tile, reported in the order a row-by-row scan first touches each one; tests connected components on a grid and avoiding recursion limits on huge regions.

A mapping service stores terrain tiles as lists of strings. Each character is either ~ (water) or . (land). Two water cells belong to the same lake if they share an edge (up, down, left, right). A lake's area is the number of water cells in it.

Part 1

def lake_areas(tile: list[str]) -> list[int]:

Return the area of every lake, ordered by the first cell of each lake encountered when scanning the tile row by row from the top, each row left to right. Return [] when there is no water.

tile = [
    "..~~.~",
    "~....~",
    "~~.~.~",
    "...~..",
    "~.~...",
]
lake_areas(tile) -> [2, 3, 3, 2, 1, 1]

Walkthrough: the scan first hits (0,2) (lake of (0,2),(0,3): area 2), then (0,5) (column 5, rows 0-2: area 3), then (1,0) ((1,0),(2,0),(2,1): area 3), then (2,3) ((2,3),(3,3): area 2), then the single cells (4,0) and (4,2).

Part 2

Hydrologists want to treat diagonally touching water as connected. Add a flag:

def lake_areas(tile: list[str], diagonal: bool = False) -> list[int]:

lake_areas(tile, diagonal=True) -> [2, 3, 3, 3, 1]
# (4,2) now touches (3,3) diagonally and joins that lake

Constraints

  • 1 <= rows, cols <= 1000; all rows have equal length.
  • A single lake may cover the entire tile (10^6 cells) or snake through it in a long, thin path. Your solution must not overflow the call stack.
  • The areas sum to the total number of ~ cells.

Hints

Hint 1

Scan in row-major order; the first unvisited water cell you see starts a new lake, which automatically gives the required ordering.

Hint 2

Flood-fill from that cell to count the lake's area, marking cells as visited.

Hint 3

Use an explicit stack or queue instead of recursion - a 10^6-cell lake would exceed Python's recursion limit.

Hint 4

Mark a cell visited when you push it, not when you pop it, to avoid pushing duplicates.

Follow-up questions

  • The tile is too large for memory and arrives one row at a time. How do you compute the areas?
  • How would you also report each lake's perimeter?
  • Water cells touching the tile border may continue into the neighboring tile. How would you stitch results across tiles?
  • Support updates where land cells become water one at a time, reporting the number of lakes after each update.