How do you solve As Far from Land as Possible?

Initialize a queue with all land cells. Perform BFS, expanding to adjacent water cells, marking them as visited by converting them to land. Track the number of BFS layers expanded; the last layer count is the maximum distance. Return -1 if the grid is all land or all water.

What pattern does As Far from Land as Possible use?

The Pattern: BFS (Multi-Source Traversal) The Heuristic: When shortest distances from multiple sources are needed simultaneously, enqueue all sources at once and perform BFS layer by layer, ensuring each node's first visit is via the shortest path from any source.

As Far from Land as Possible — BFS

Q: What is the time complexity of As Far from Land as Possible?

O(n^2). Each cell is enqueued and dequeued at most once during BFS, and each neighbor check is constant time, resulting in O(n^2) total operations for an n x n grid.

Problem

Given an n x n grid containing 0s (water) and 1s (land), return the maximum distance from any water cell to the nearest land cell. If no water or no land exists, return -1.

n == grid.length
n == 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

Starting from all land cells simultaneously, the BFS expands layer by layer into water cells. The farthest water cell from any land is at distance 2. The algorithm initializes the queue with all land cells, then explores neighbors in waves. The critical moment is when the BFS reaches the last layer of water cells, which determines the maximum distance.

Approach

Straightforward Solution

A naive approach would run BFS from each water cell to find the nearest land, resulting in O(n^4) time complexity, which is infeasible for large grids.

Core Observation

The shortest distance from any water cell to land can be found by simultaneously expanding from all land cells using BFS. This multi-source BFS treats all land cells as starting points and explores outward in layers, ensuring the first time a water cell is reached is via the shortest path.

Path to Optimal

Preview

Recognizing that BFS from each water cell is inefficient, the key insight is to reverse the problem: start BFS from all land cells simultaneously. This multi-source BFS expands outward, marking distances to water cells as layers increase…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize a queue with all land cells. Perform BFS, expanding to adjacent water cells, marking them as visited by converting them to land…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n^2)

Each cell is enqueued and dequeued at most once during BFS, and each neighbor check is constant time, resulting in O(n^2) total operations for an n x n grid.

Space

O(n^2)

The queue can hold up to O(n^2) cells in the worst case, and the grid is modified in-place to mark visited cells, so auxiliary space is O(n^2) due to the queue.

Solution

Python

1class Solution:
  def maxDistance(self, grid: List[List[int]]) -> int:
      n = len(grid)
      q = deque()
5
      for r in range(n):
          for c in range(n):
              if grid[r][c] == 1:
                  q.append((r, c))
10
      if not q or len(q) == n * n:
          return -1
13
      directions = [(1,0), (-1,0), (0,1), (0,-1)]
      dist = -1
16
      while q:
          dist += 1
19
          for _ in range(len(q)):
              r, c = q.popleft()
22
              for dr, dc in directions:
                  nr, nc = r + dr, c + dc
25
                  if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                      grid[nr][nc] = 1
                      q.append((nr, nc))
29
      return dist

Step-by-Step Solution

1

Collect All Land Cells as BFS Starting Points

3n = len(grid)
4q = deque()
6for r in range(n):
7    for c in range(n):
8        if grid[r][c] == 1:
9            q.append((r, c))
11if not q or len(q) == n * n:
12    return -1

Objective

To identify all land cells and enqueue them as the initial BFS frontier.

Key Insight

By treating all land cells as sources, the BFS can expand outward simultaneously, efficiently computing the shortest distance to water cells. This multi-source initialization avoids repeated BFS from each water cell, drastically reducing time complexity.

Interview Quick-Check

Core Logic

Enqueueing all land cells at once sets up a multi-source BFS that finds shortest distances to water cells in a single pass.

State & Boundaries

Check if the queue is empty or full (all land) to handle edge cases where no valid distance exists.

Common Pitfalls & Bugs

Forgetting to enqueue all land cells initially leads to incorrect distance calculations or incomplete BFS.

2

Expand BFS Frontier Layer by Layer to Measure Distance

To perform BFS expansion from land cells into water cells, tracking the distance in layers.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 9 Critical

q.append((r, c))

Add land cell coordinates to the BFS queue.

This line is critical because it seeds the BFS with all land cells, ensuring the search expands simultaneously from all sources and finds shortest distances efficiently.

Line 18 Critical

dist += 1

Increment distance at the start of each BFS layer.

Incrementing distance at the start of each BFS layer is the core mechanism that measures how far the BFS has expanded from land, directly yielding the maximum distance to water.

Line 26 Critical

if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:

Check if neighbor is within bounds and is water.

This compound condition is critical to BFS correctness, ensuring only valid, unvisited water cells are enqueued, preventing infinite loops and incorrect distance calculations.

Full line-by-line criticality + rationale for all 20 lines available on Pro.

Test Your Understanding

Why does starting BFS from all land cells simultaneously guarantee the shortest distance to water cells?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct As Far from Land as Possible from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the As Far from Land as Possible drill

or drill a free problem

1	`class Solution:`
2	`def maxDistance(self, grid: List[List[int]]) -> int:`
3	`n = len(grid)`
4	`q = deque()`
5
6	`for r in range(n):`
7	`for c in range(n):`
8	`if grid[r][c] == 1:`
9	`q.append((r, c))`
10
11	`if not q or len(q) == n * n:`
12	`return -1`
13
14	`directions = [(1,0), (-1,0), (0,1), (0,-1)]`
15	`dist = -1`
16
17	`while q:`
18	`dist += 1`
19
20	`for _ in range(len(q)):`
21	`r, c = q.popleft()`
22
23	`for dr, dc in directions:`
24	`nr, nc = r + dr, c + dc`
25
26	`if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:`
27	`grid[nr][nc] = 1`
28	`q.append((nr, nc))`
29
30	`return dist`

3	`n = len(grid)`
4	`q = deque()`
6	`for r in range(n):`
7	`for c in range(n):`
8	`if grid[r][c] == 1:`
9	`q.append((r, c))`
11	`if not q or len(q) == n * n:`
12	`return -1`