Problem Description

You are given an n x n grid where each cell contains either 0 (representing water) or 1 (representing land). Your task is to find a water cell that is as far as possible from any land cell, and return this maximum distance.

The distance between two cells is calculated using Manhattan distance: for two cells at positions (x0, y0) and (x1, y1), the distance is |x0 - x1| + |y0 - y1|.

If the grid contains only water cells (no land) or only land cells (no water), return -1.

The solution uses a multi-source BFS approach. First, all land cells are added to a queue as starting points. If the queue is empty (no land) or contains all cells in the grid (no water), the function returns -1.

The BFS then proceeds level by level. In each iteration:

• All cells at the current distance level are processed
• For each cell, its four adjacent neighbors (up, down, left, right) are checked
• If a neighbor is a water cell (value 0), it's marked as visited by changing it to 1 and added to the queue for the next level
• After processing each level, the distance counter increases by 1

The process continues until all reachable water cells have been visited. The final distance value represents the maximum distance from any water cell to the nearest land cell.

The key insight is that by starting from all land cells simultaneously and expanding outward, the last water cells to be reached are necessarily the ones furthest from any land.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The grid can be viewed as a graph where each cell is a node and adjacent cells (up, down, left, right) are connected by edges. We need to traverse this graph to find distances.

Is it a tree?

• No: The grid structure is not a tree - it can have multiple paths between cells and doesn't have a hierarchical parent-child relationship.

Is the problem related to directed acyclic graphs?

• No: The grid allows movement in all four directions, and the problem isn't about directed edges or acyclic properties.

Is the problem related to shortest paths?

• Yes: We need to find the shortest distance from each water cell to the nearest land cell. The maximum of these shortest distances is our answer.

Is the graph Weighted?

• No: All edges have the same weight (distance of 1 between adjacent cells). The Manhattan distance is simply the count of steps taken.

BFS

• Yes: Since we have an unweighted graph and need to find shortest paths, BFS is the appropriate algorithm.

Conclusion: The flowchart suggests using BFS for this problem. Specifically, we use multi-source BFS starting from all land cells simultaneously, which efficiently computes the shortest distance from each water cell to the nearest land cell. The last water cells reached by the BFS expansion will be the ones furthest from any land.

Intuition

The key insight is to reverse our thinking about the problem. Instead of finding the distance from each water cell to the nearest land, we can start from all land cells and expand outward simultaneously.

Think of it like this: imagine all land cells are sources of a "wave" that spreads outward at the same speed. Each wave moves one cell per time unit. Water cells get "hit" by the wave when it reaches them. The water cells that get hit last are necessarily the ones furthest from any land.

This multi-source BFS approach is efficient because:

1. We only need to traverse the grid once, rather than running BFS from each water cell individually
2. By starting from all land cells at once, we naturally compute the minimum distance to land for each water cell
3. The last cells to be reached in our BFS traversal are guaranteed to be the furthest from any land

The algorithm works by:

• Initially marking all land cells as "distance 0" by adding them to the queue
• In each iteration, we process all cells at the current distance level
• We mark newly reached water cells and add them to the queue for the next level
• The number of levels (iterations) we go through equals the maximum distance

This transforms a potentially complex problem of finding maximum of minimums into a simple level-order traversal where the answer is just the number of levels we traverse.

Learn more about Breadth-First Search and Dynamic Programming patterns.

Solution Approach

The implementation uses a multi-source BFS approach with the following key components:

Data Structures:

• A deque (double-ended queue) to store cells for BFS traversal
• The original grid itself is modified to mark visited cells

Initial Setup:

q = deque((i, j) for i in range(n) for j in range(n) if grid[i][j])

We scan the entire grid and add all land cells (cells with value 1) to the queue. These serve as our starting points for the BFS.

Edge Case Handling:

if len(q) in (0, n * n):
    return -1

If the queue is empty (no land) or contains all cells (no water), we return -1 as specified.

BFS Traversal: The BFS proceeds level by level with ans initialized to -1:

while q:
    for _ in range(len(q)):
        i, j = q.popleft()
        for a, b in pairwise(dirs):
            x, y = i + a, j + b
            if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:
                grid[x][y] = 1
                q.append((x, y))
    ans += 1

Direction Handling: The dirs = (-1, 0, 1, 0, -1) array with pairwise creates the four directional moves:

• (-1, 0) for up
• (0, 1) for right
• (1, 0) for down
• (0, -1) for left

Level Processing:

• The inner loop for _ in range(len(q)) ensures we process all cells at the current distance level before moving to the next
• When we find an unvisited water cell (grid[x][y] == 0), we mark it as visited by setting it to 1 and add it to the queue
• After each level is completely processed, we increment ans

Space Optimization: Instead of using a separate visited array, the solution cleverly reuses the input grid to mark visited cells by changing water cells (0) to land cells (1) as they're visited.

The final ans represents the number of levels traversed, which equals the maximum distance from any water cell to the nearest land cell.

Example Walkthrough

Let's walk through a small 3x3 grid example to illustrate the multi-source BFS approach:

Initial Grid:
1 0 0
0 0 0  
0 0 1

Step 1: Initial Setup

• Scan the grid and add all land cells (value 1) to the queue
• Queue initially contains: [(0,0), (2,2)] - the two land cells
• Since we have both land and water, we proceed with BFS
• ans = -1

Step 2: First BFS Level (Distance 0)

• Process all cells currently in queue: (0,0) and (2,2)
• From (0,0), check neighbors:
  • Up: out of bounds
  • Right: (0,1) is water (0) → mark as visited (set to 1), add to queue
  • Down: (1,0) is water (0) → mark as visited (set to 1), add to queue
  • Left: out of bounds
• From (2,2), check neighbors:
  • Up: (1,2) is water (0) → mark as visited (set to 1), add to queue
  • Right: out of bounds
  • Down: out of bounds
  • Left: (2,1) is water (0) → mark as visited (set to 1), add to queue
• Queue for next level: [(0,1), (1,0), (1,2), (2,1)]
• Increment ans = 0

Grid after Level 0:

1 1 0
1 0 1  
0 1 1

Step 3: Second BFS Level (Distance 1)

• Process cells: (0,1), (1,0), (1,2), (2,1)
• From (0,1):
  • Right: (0,2) is water → mark as visited, add to queue
• From (1,0):
  • Right: (1,1) is water → mark as visited, add to queue
• From (1,2):
  • Left: (1,1) already marked as visited this round
• From (2,1):
  • Left: (2,0) is water → mark as visited, add to queue
• Queue for next level: [(0,2), (1,1), (2,0)]
• Increment ans = 1

Grid after Level 1:

1 1 1
1 1 1  
1 1 1

Step 4: Third BFS Level (Distance 2)

• Process cells: (0,2), (1,1), (2,0)
• All neighbors are already visited (marked as 1)
• No new cells added to queue
• Increment ans = 2

Step 5: Termination

• Queue is empty, BFS completes
• Return ans = 2

The cells (0,2), (1,1), and (2,0) were the last to be reached, confirming they are the furthest water cells from any land. Each has a Manhattan distance of 2 to the nearest land cell. For example, (1,1) is distance 2 from both (0,0) and (2,2).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm uses BFS (Breadth-First Search) starting from all land cells simultaneously. In the worst case, every cell in the n × n grid will be visited exactly once. The initial queue construction takes O(n²) time to iterate through all cells. During the BFS traversal, each cell is added to the queue at most once and processed once, resulting in O(n²) operations. For each cell processed, we check 4 directions, which is O(1) per cell. Therefore, the overall time complexity is O(n²).

Space Complexity: O(n²)

The space complexity is dominated by the queue q which, in the worst case, can contain all cells of the grid. This happens when all cells are initially land cells (containing 1), making the queue size n × n. Even in a more typical case where the queue grows during BFS execution, it can still hold up to O(n²) cells at once. The dirs tuple uses constant space O(1). Since we're modifying the input grid in-place, no additional grid space is needed. Therefore, the overall space complexity is O(n²).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Distance Initialization

A common mistake is initializing the distance counter to 0 instead of -1. Since we increment the distance after processing each level (including the initial land cells), starting at 0 would give us a result that's off by one.

Wrong:

max_distance = 0  # Incorrect initialization
while queue:
    # ... BFS logic ...
    max_distance += 1
return max_distance  # Returns distance + 1

Correct:

max_distance = -1  # Correct initialization
while queue:
    # ... BFS logic ...
    max_distance += 1
return max_distance

2. Not Processing Level by Level

Failing to process all cells at the current distance level before moving to the next level will result in incorrect distance calculations. The inner loop that processes len(queue) cells is crucial.

Wrong:

while queue:
    current_row, current_col = queue.popleft()  # Processes cells one by one
    for delta_row, delta_col in directions:
        # ... check neighbors ...
    max_distance += 1  # Increments for each cell, not each level!

Correct:

while queue:
    current_level_size = len(queue)
    for _ in range(current_level_size):  # Process entire level
        current_row, current_col = queue.popleft()
        # ... check neighbors ...
    max_distance += 1  # Increments once per level

3. Modifying the Queue Size During Iteration

Using range(len(queue)) directly without storing the size first can lead to issues if the queue is modified during iteration.

Wrong:

for _ in range(len(queue)):  # If queue is modified, this could behave unexpectedly
    # ... process cells and add to queue ...

Correct:

current_level_size = len(queue)  # Store size before iteration
for _ in range(current_level_size):
    # ... process cells and add to queue ...

4. Using a Separate Visited Array Unnecessarily

While not incorrect, using additional space for tracking visited cells is unnecessary since we can modify the grid in-place. This wastes O(n²) extra space.

Inefficient:

visited = [[False] * n for _ in range(n)]
# ... in BFS loop ...
if not visited[next_row][next_col] and grid[next_row][next_col] == 0:
    visited[next_row][next_col] = True
    queue.append((next_row, next_col))

Efficient:

# Reuse the grid itself
if grid[next_row][next_col] == 0:
    grid[next_row][next_col] = 1  # Mark as visited by changing value
    queue.append((next_row, next_col))

5. Forgetting Edge Case Validation

Not checking for grids with all water or all land will cause the BFS to either never start or return an incorrect result.

Wrong:

# Missing edge case check
queue = deque()
for row in range(n):
    for col in range(n):
        if grid[row][col] == 1:
            queue.append((row, col))
# Proceeds with BFS even if queue is empty or full

Correct:

land_count = len(queue)
if land_count == 0 or land_count == n * n:
    return -1  # Handle edge cases before BFS