Area of the biggest patch of land

Graphs Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
grid = ["##.", ".#.", "..#"]
seen = set()
sizes = []
for r in range(3):
    for c in range(3):
        if grid[r][c] == "#" and (r, c) not in seen:
            seen.add((r, c))
            todo, size = [(r, c)], 0
            while todo:
                y, x = todo.pop()
                size += 1
                for dy, dx in steps:
                    ny, nx = y + dy, x + dx
                    if (0 <= ny < 3 and 0 <= nx < 3
                            and grid[ny][nx] == "#"
                            and (ny, nx) not in seen):
                        seen.add((ny, nx))
                        todo.append((ny, nx))
            sizes.append(size)
print(sizes)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [3, 1]

Right: the top three cells join; the corner cell is alone.

Diagonal contact does not join patches, so the bottom-right cell stays separate.

Why not the others?
  • B [4]. (2, 2) only touches (1, 2) and (2, 1), which are water.
  • C [2, 1, 1]. (1, 1) touches (0, 1), so three cells form one patch.

30-second answer

Same flood as counting patches, but count the cells each flood reaches and keep the largest. Each cell is visited once: O(R·C) time and space.

Practise saying it · 30 s. No recording, just a timer

Explain how to find the largest patch.

Say your answer out loud, then check which of these points you covered:

  • Flood each patch
  • Count its cells
  • O(R·C)

Deep dive

Reusing a known pattern with a small twist is exactly what interviewers hope to see; say so.

Counting cells as they are popped gives the size; counting on push works too if you are consistent.

Union-find with sizes also works and gives sizes for free.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
STEPS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def biggest_patch(grid: list[str]) -> int:
    """Largest number of 4-way connected '#' cells."""
    rows, cols = len(grid), len(grid[0]) if grid else 0
    seen: set[tuple[int, int]] = set()
    best = 0
    for r, row in enumerate(grid):
        for c, cell in enumerate(row):
            if cell != "#" or (r, c) in seen:
                continue
            seen.add((r, c))
            todo, area = [(r, c)], 0
            while todo:
                y, x = todo.pop()
                area += 1
                for dy, dx in STEPS:
                    ny, nx = y + dy, x + dx
                    inside = 0 <= ny < rows and 0 <= nx < cols
                    if (inside and grid[ny][nx] == "#"
                            and (ny, nx) not in seen):
                        seen.add((ny, nx))
                        todo.append((ny, nx))
            best = max(best, area)
    return best

Common mistakes

  • Resetting the seen set for each flood, which revisits cells.
  • Returning the count of patches instead of the size.

Senior take & follow-ups

Point out that this is the patch-counting flood plus a counter.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if you may turn one water cell into land?

    Show hint

    Label patches with sizes, then for each water cell add the sizes of distinct neighbouring patches.

  2. How would you find the perimeter of a patch?

    Show hint

    Count land-to-water or land-to-edge sides.

What each operation costs: Breadth First Search · Depth First Search · Topological Sort · Dijkstra Algorithm

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.