As Far From Land As Possible — Multi-Source BFS Distance (LC 1162)

Problem Statement#

LeetCode 1162 — As Far From Land As Possible (Medium)

Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or no water exists in the grid, return -1.

The distance used in this problem is the Manhattan distance: the distance between (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

Constraints:

• n == grid.length == grid[i].length
• 1 <= n <= 100
• grid[i][j] is 0 or 1.

Example:

Input: grid = [[1,0,1],
               [0,0,0],
               [1,0,1]]
Output: 2
Explanation: The cell (1, 1) is as far as possible from all land. Distance to nearest land = 2.
 
Input: grid = [[1,0,0],
               [0,0,0],
               [0,0,0]]
Output: 4
Explanation: The cell (2, 2) is the farthest from land at distance 4.

Why This Problem Matters#

As Far From Land As Possible is the maximum-distance counterpart of LC 542 (01 Matrix). While LC 542 returns a full distance matrix, this one asks for the largest such distance over all water cells. Both problems are solved by identical multi-source BFS — the only difference is what you do with the distances.

This problem is a Day-1 favorite at Google, Amazon, and Meta because it tests three skills concurrently: choosing BFS over DFS for shortest distances, multi-source seeding, and proper handling of the "all land or all water" edge case. Mastering this template makes a whole family of grid-spread problems trivial — Rotting Oranges, Walls and Gates, 01 Matrix, and Shortest Bridge all reduce to the same core loop.

The Core Insight#

The distance from any water cell to its nearest land cell equals the BFS depth of that cell when BFS is seeded simultaneously from every land cell. This works because:

• BFS from a single source gives the shortest distance to that source.
• BFS from multiple sources gives the shortest distance to the nearest source for every reachable cell.

So the algorithm is:

1. Seed the queue with every land cell.
2. Run level-order BFS, incrementing a distance counter once per BFS level.
3. After the BFS terminates, the value of distance (minus the initial pad if you initialize at -1, etc.) is the maximum.

We also need to detect the "no land" or "no water" case. If the queue starts empty (no land) or stays full of land (no water expansion happens), return -1.

Why distance counts BFS levels, not Manhattan distance directly? Because BFS in a grid with 4-directional moves and unit edges equals Manhattan distance. The BFS level at which a cell is first reached is exactly its Manhattan distance to the nearest source.

Visual Dry Run#

Grid:

1 0 0
0 0 0
0 0 0

Seed queue with [(0, 0)] (only land cell). distance = -1 initially (so we increment to 0 on first land level, 1 on next, etc.).

Final answer: 4. The water cell (2, 2) is exactly 4 Manhattan steps from (0, 0).

Solution (Optimal)#

Python#

from collections import deque
 
class Solution:
    def maxDistance(self, grid: list[list[int]]) -> int:
        N = len(grid)
        queue = deque()
 
        # 1) seed with every land cell
        for r in range(N):
            for c in range(N):
                if grid[r][c] == 1:
                    queue.append((r, c))
 
        # all-land or all-water -> -1
        if len(queue) == 0 or len(queue) == N * N:
            return -1
 
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        distance = -1
 
        # 2) level-order BFS expanding into water
        while queue:
            distance += 1
            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         # mark visited (avoid revisits)
                        queue.append((nr, nc))
 
        return distance

JavaScript#

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
    const N = grid.length;
    const queue = [];
 
    // seed all land cells
    for (let r = 0; r < N; r++) {
        for (let c = 0; c < N; c++) {
            if (grid[r][c] === 1) queue.push([r, c]);
        }
    }
 
    // edge case: all land or all water
    if (queue.length === 0 || queue.length === N * N) return -1;
 
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    let distance = -1;
    let head = 0;
 
    while (head < queue.length) {
        distance++;
        const levelEnd = queue.length;
        while (head < levelEnd) {
            const [r, c] = queue[head++];
            for (const [dr, dc] of dirs) {
                const nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
                if (grid[nr][nc] !== 0) continue;
                grid[nr][nc] = 1;                // mark visited
                queue.push([nr, nc]);
            }
        }
    }
    return distance;
};

Time Complexity: O(n^2) — each cell enqueued once. Space Complexity: O(n^2) for the queue worst case.

Common Mistakes#

1. Single-source BFS from each land cell. O(N^4) — times out on n=100 inputs.
2. Off-by-one on distance. Initialize distance = -1 so that after processing all land cells (level 0) it sits at 0, and increments correctly per level. Initialize at 0 if you increment after popping — be consistent.
3. Forgetting the all-land or all-water case. Both must return -1 per spec.
4. Marking water as visited too late. Mark it immediately after enqueueing or you will revisit cells from multiple parents.
5. Using DFS. DFS does not yield shortest distances out of the box.

Interview Tips#

• Lead with the LC 542 connection. "This is essentially LC 01 Matrix where I return the maximum distance instead of the matrix."
• Explain why level-counting works. BFS expands one level per minute/step; distance equals depth.
• Mention the early termination. You can stop expanding once the queue is empty — the last value of distance is the answer.
• Discuss DP alternative. Two-pass DP (top-left + bottom-right sweeps with min(top, left) + 1) achieves the same complexity without a queue.

Follow-up Questions#

1. What if the grid has obstacles (cells you cannot pass through)? Treat obstacles as already-visited so BFS cannot route through them.
2. What is the closest water cell from land instead? Same algorithm with seeds and targets swapped.
3. K-th farthest water cell instead of the farthest? Track the k largest distances using a heap during BFS.
4. Diagonal moves allowed? Switch to 8-directional deltas; same algorithm.
5. Streaming version where land changes over time? Use Union-Find or incremental BFS; full re-BFS works for moderate update frequencies.

Key Takeaways#

• As Far From Land As Possible is multi-source BFS seeded from every land cell, with the answer being the deepest BFS level reached.
• Always handle the all-land and all-water edge cases — both return -1.
• Initialize distance carefully: -1 if you increment before processing a level, 0 if after.
• Mark water cells visited immediately when enqueued to prevent duplicate work.
• The 4-directional BFS distance equals Manhattan distance — that is why this works without explicit distance tracking per cell.
• This algorithm is the foundation for LC 542, LC 994, LC 286, and LC 934. Master one, master all.