Count the separate patches of land on a map

Graphs Mid-level Python 3.13+ Kotlin 2.4+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
grid = ["##.", "#..", "..#"]
land = {(r, c) for r, row in enumerate(grid)
        for c, ch in enumerate(row) if ch == "#"}
print(len(land), (2, 2) in land, (1, 1) in land)

Options

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

Show answer

Answer: A 4 True False

Right: four land cells; (2, 2) is land and (1, 1) is water.

Three of the four land cells touch each other; the corner cell touches none of them, so the map has two patches.

Why not the others?
  • B 3 True False. Count again: the top-left patch has three cells plus the corner cell.
  • C 4 False True. Row 2 is '..#', so column 2 is land.
The map is scanned row by row; each land cell not yet seen starts a new patch and a flood marks every land cell touching it, on two small maps.

Steps come from running the Python solution.

Text version

Two patches:

Grid (✕ = blocked): □□✕ / □✕✕ / ✕✕□.

  1. Visit (0, 0), frontier 1. New patch 1 starts at row 0, column 0
  2. Visit (1, 0), (0, 1), frontier 2. Patch 1: 2 more land cells next to row 0, column 0
  3. Visit (2, 2), frontier 1. New patch 2 starts at row 2, column 2

Result: 2

Ring of land:

Grid (✕ = blocked): □□□ / □✕□ / □□□.

  1. Visit (0, 0), frontier 1. New patch 1 starts at row 0, column 0
  2. Visit (1, 0), (0, 1), frontier 2. Patch 1: 2 more land cells next to row 0, column 0
  3. Visit (0, 2), frontier 2. Patch 1: 1 more land cell next to row 0, column 1
  4. Visit (1, 2), frontier 2. Patch 1: 1 more land cell next to row 0, column 2
  5. Visit (2, 2), frontier 2. Patch 1: 1 more land cell next to row 1, column 2
  6. Visit (2, 1), frontier 2. Patch 1: 1 more land cell next to row 2, column 2
  7. Visit (2, 0), frontier 2. Patch 1: 1 more land cell next to row 2, column 1

Result: 1

30-second answer

Scan every cell. When you meet land you have not visited, count a new patch and flood it: walk all land reachable from it with a stack or queue, marking cells as seen. Each cell is visited a constant number of times, so it is O(R·C) time and O(R·C) space for the seen set.

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

Explain how to count patches on a grid.

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

  • Scan cells
  • Flood each new patch
  • O(R·C)

Deep dive

Marking a cell seen when it is pushed (not when popped) stops it being pushed twice.

Recursive DFS is shorter but can hit Python's recursion limit on a big all-land map.

Union-find also works and suits maps where land is added over time.

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


def count_patches(grid: list[str]) -> int:
    """'#' is land and '.' is water; count 4-way connected land."""
    rows, cols = len(grid), len(grid[0]) if grid else 0
    seen: set[tuple[int, int]] = set()
    patches = 0
    for r, row in enumerate(grid):
        for c, cell in enumerate(row):
            if cell != "#" or (r, c) in seen:
                continue
            patches += 1
            seen.add((r, c))
            todo = [(r, c)]
            while todo:
                y, x = todo.pop()
                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))
    return patches

Kotlin Ran on Kotlin 2.4.21 · JDK 21.0.12.1
Kotlin 2.4
val STEPS = listOf(1 to 0, -1 to 0, 0 to 1, 0 to -1)

fun countPatches(grid: List<String>): Int {
    val seen = HashSet<Pair<Int, Int>>()
    var patches = 0
    for ((r, row) in grid.withIndex()) {
        for ((c, cell) in row.withIndex()) {
            if (cell != '#' || !seen.add(r to c)) continue
            patches++
            val todo = ArrayDeque(listOf(r to c))
            while (todo.isNotEmpty()) {
                val (y, x) = todo.removeLast()
                for ((dy, dx) in STEPS) {
                    val next = (y + dy) to (x + dx)
                    val line = grid.getOrNull(next.first) ?: continue
                    if (line.getOrNull(next.second) != '#') continue
                    if (seen.add(next)) todo.addLast(next)
                }
            }
        }
    }
    return patches
}

Common mistakes

  • Counting diagonal neighbours when the question says four directions.
  • Changing the input map to mark visits without asking whether that is allowed.

Senior take & follow-ups

Say 'each cell is pushed once' to justify O(R·C). It is the standard argument for grid searches.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if land is added one cell at a time and you report the count after each?

    Show hint

    Union-find: each new cell joins its land neighbours, O(α) per union.

  2. How would you return the size of the biggest patch?

    Show hint

    Count cells during each flood and keep the maximum.

See it animated on iPhone (Depth First Search in DSA Master - Data & Algorithms)

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.