As Far from Land as Possible: Multi-Source BFS Pattern

You are given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land. Find the water cell whose distance to the nearest land cell is maximized, and return that distance. The distance is measured using Manhattan distance: |r1 - r2| + |c1 - c2|. If no water or no land exists in the grid, return -1.

This is LeetCode 1162: As Far from Land as Possible, and it is a textbook application of multi-source BFS. The technique it teaches, computing shortest distances from multiple starting points simultaneously, is the same one behind problems like "Rotting Oranges" and "01 Matrix."

Why this problem matters

A naive approach would be: for every water cell, run BFS to find the nearest land cell, then take the maximum across all water cells. That works, but it is O(n^4) for an n x n grid. Each BFS is O(n^2), and there could be O(n^2) water cells.

Multi-source BFS flips the perspective. Instead of searching from each water cell, you search from all land cells at once. A single BFS pass computes the shortest distance from every water cell to its nearest land cell. The answer is just the maximum value you encounter.

This "invert the search direction" idea is one of the most useful patterns in grid BFS problems.

The key insight

Instead of asking "how far is this water cell from the nearest land?", you ask "how far does the BFS wavefront travel from all land cells before it reaches every water cell?"

You start by adding every land cell to the BFS queue with distance 0. Then you process the queue level by level. At each level, you expand to unvisited water neighbors and assign them the current distance plus one. When the queue is empty, the last distance you assigned is the answer.

The algorithm:

1. Scan the grid. Add every land cell (value 1) to the queue. Mark it as visited.
2. Run BFS level by level. For each cell in the current level, check its four neighbors. If a neighbor is water and unvisited, mark it with the current distance plus one and add it to the queue.
3. Track the maximum distance assigned.
4. When the queue is empty, return the maximum distance. If no water was reached (all land) or no land existed (empty queue from the start), return -1.

The solution

from collections import deque

def max_distance(grid: list[list[int]]) -> int:
    n = len(grid)
    queue = deque()

    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:
                queue.append((r, c))

    if len(queue) == 0 or len(queue) == n * n:
        return -1

    dist = -1
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while queue:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1
                    queue.append((nr, nc))
        dist += 1

    return dist

Let's walk through what each piece does.

The first loop scans the grid and seeds the BFS queue with every land cell. This is the multi-source initialization: all land cells enter the queue at distance 0 simultaneously.

The early return handles two edge cases. If no land exists, BFS cannot start. If no water exists, there is no water cell to measure distance for. Both return -1.

The BFS loop processes one full level at a time using the for _ in range(len(queue)) pattern. Each level corresponds to one unit of Manhattan distance. When we process a cell, we check its four neighbors. If a neighbor is water (value 0), we mark it as land (value 1) to indicate "visited" and add it to the queue. This prevents any cell from being enqueued twice.

The dist variable starts at -1 and increments after each level. Since the first level processes the original land cells (distance 0), dist ends up at 0 after that level. After the next level, it is 1, and so on. When BFS finishes, dist holds the maximum distance reached.

Visual walkthrough

Let's trace through a 4x4 grid with land at (0,0) and (2,2). Watch how BFS radiates outward from both land cells simultaneously, assigning distances level by level.

Notice that both land cells spread at the same time. By the time BFS finishes, every water cell has been assigned the shortest Manhattan distance to its nearest land cell. The maximum distance encountered is 3, so that is the answer.

Complexity analysis

Time is O(n^2) where n is the side length of the grid. The initial scan visits every cell once. The BFS also visits each cell at most once, because we mark cells as visited before enqueueing them. Total work is proportional to the number of cells.

Space is O(n^2) in the worst case. If every cell is land except one, the queue starts with nearly n^2 entries. In practice, the queue holds at most the size of the BFS frontier, but the worst case is the full grid.

The building blocks

1. Multi-source BFS initialization

The pattern of seeding a BFS queue with multiple starting nodes instead of one:

queue = deque()
for r in range(n):
    for c in range(n):
        if grid[r][c] == 1:
            queue.append((r, c))

This is the core difference between single-source and multi-source BFS. Everything else, the level-by-level processing, the neighbor exploration, the visited marking, stays exactly the same. You will reuse this initialization pattern in "Rotting Oranges," "01 Matrix," "Walls and Gates," and any problem that asks for shortest distances from multiple sources.

2. Level-by-level BFS distance tracking

The pattern of processing all nodes at the current depth before moving to the next:

dist = -1
while queue:
    for _ in range(len(queue)):
        node = queue.popleft()
        for neighbor in get_neighbors(node):
            if unvisited(neighbor):
                mark_visited(neighbor)
                queue.append(neighbor)
    dist += 1

Starting dist at -1 and incrementing after each full level is a clean way to track BFS depth. The first level processes the original sources (distance 0), so dist becomes 0. Each subsequent level increments by one. When BFS terminates, dist is the maximum distance from any source.

Edge cases

Before submitting, think through these scenarios:

• All land: every cell is 1. No water cell exists, so return -1.
• All water: every cell is 0. No land cell exists, so BFS cannot start. Return -1.
• Single land cell in corner: BFS radiates outward. The farthest water cell is at the opposite corner, with distance (n - 1) + (n - 1) = 2 * (n - 1).
• Land cells adjacent: they share the BFS wavefront. Cells between them get smaller distances than cells on the outer edges.
• 1x1 grid: [[0]] returns -1 (no land). [[1]] returns -1 (no water).
• 2x2 grid with one land cell: the farthest water cell is at the opposite corner, distance 2.

From understanding to recall

You have seen how multi-source BFS solves "As Far from Land as Possible": seed the queue with all land cells, expand level by level, and track the maximum distance. The logic mirrors "Rotting Oranges" almost exactly, with distances replacing minutes and land replacing rotten oranges.

The details that trip people up are subtle. Do you start dist at 0 or -1? Do you check for all-land and all-water before or after BFS? Do you mark visited before or after enqueueing? These are not conceptual gaps. They are recall gaps, and they cost people offers.

Spaced repetition is how you close them. You practice writing the multi-source BFS initialization, the level-by-level loop, and the edge case checks from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "maximum distance from multiple sources" in a problem description, and the BFS template flows out without hesitation.

Related posts

• Rotting Oranges - Multi-source BFS spreading from multiple origins, the closest sibling to this problem
• 01 Matrix - Same multi-source BFS pattern for computing nearest distance to a target value
• Shortest Bridge - Combines flood fill with multi-source BFS to find shortest path between two islands

CodeBricks breaks "As Far from Land as Possible" into its multi-source BFS initialization and level-by-level distance tracking building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a BFS problem shows up in your interview, you do not think about it. You just write it.