As Far from Land as Possible

▶

Steps

setup

Initialize distance matrix and queue

Create a distance matrix with -1 for all cells initially and an empty queue to hold land cells.

💡 Setting up the distance matrix and queue prepares for BFS by marking all water as unvisited and collecting land cells.

Line:

n = len(grid)
dist = [[-1]*n for _ in range(n)]
queue = deque()

💡 All cells start as unvisited water (-1 distance), and the queue is ready to hold land cells.

setup

Enqueue all land cells and set their distance to 0

Scan the grid, mark land cells with distance 0, change their state to 'in_queue', and enqueue them.

💡 Starting BFS from all land cells simultaneously allows distance propagation to water cells.

Line:

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

💡 Land cells are BFS sources with distance zero; queue now holds all these starting points.

setup

Check for edge cases: all land or all water

If the queue is empty (no land) or full (all land), return -1 immediately.

💡 This prevents unnecessary BFS when no water or no land exists.

Line:

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

💡 The problem requires at least one land and one water cell to find a meaningful distance.

traverse

Start BFS: dequeue first land cell (0,0)

Dequeue cell (0,0) from the queue and mark it as processing.

💡 Processing each cell in BFS order expands the search frontier.

Line:

r, c = queue.popleft()

💡 The BFS explores neighbors of (0,0) next.

compare

Check neighbor (1,0) of (0,0)

Check if neighbor (1,0) is within bounds and unvisited water (distance -1).

💡 Only unvisited water neighbors get their distance updated and enqueued.

Line:

if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:

💡 BFS expands to adjacent water cells, increasing their distance by 1.

expand

Update distance and enqueue neighbor (1,0)

Set distance of (1,0) to 1 and enqueue it; mark node as 'in_queue' and edge as 'traversed'.

💡 Updating distance and queueing neighbor expands BFS frontier.

Line:

dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))

💡 Distance increments by 1 from the current cell to its neighbor.

compare

Check neighbor (0,1) of (0,0)

Check if neighbor (0,1) is valid and unvisited water.

💡 We explore all four neighbors to find new water cells to update.

Line:

if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:

💡 BFS continues expanding to adjacent water cells.

expand

Update distance and enqueue neighbor (0,1)

Set distance of (0,1) to 1 and enqueue it; mark node as 'in_queue' and edge as 'traversed'.

💡 This expands BFS frontier to another water cell.

Line:

dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))

💡 Distance increments by 1 from the current cell to its neighbor.

traverse

Finish processing (0,0), mark as done

All neighbors of (0,0) checked; mark node as done and remove from processing.

💡 Marking done means this cell's neighbors are fully explored.

Line:

No explicit code line; after neighbors loop ends.

💡 BFS moves on to next cell in queue.

traverse

Dequeue next land cell (0,2) and process neighbors

Dequeue (0,2), mark processing, and check neighbors for water to update.

💡 BFS continues expanding from all land cells and discovered water cells.

Line:

r, c = queue.popleft()

💡 Exploring neighbors of (0,2) will update distances for adjacent water cells.

from collections import deque
from typing import List

def maxDistance(grid: List[List[int]]) -> int:
    n = len(grid)  # STEP 1
    dist = [[-1]*n for _ in range(n)]  # STEP 1
    queue = deque()  # STEP 1

    for r in range(n):  # STEP 2
        for c in range(n):  # STEP 2
            if grid[r][c] == 1:  # STEP 2
                dist[r][c] = 0  # STEP 2
                queue.append((r, c))  # STEP 2

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

    directions = [(1,0), (-1,0), (0,1), (0,-1)]  # STEP 4
    max_dist = -1  # STEP 4

    while queue:  # STEP 4
        r, c = queue.popleft()  # STEP 4
        for dr, dc in directions:  # STEP 5
            nr, nc = r + dr, c + dc  # STEP 5
            if 0 <= nr < n and 0 <= nc < n and dist[nr][nc] == -1:  # STEP 6
                dist[nr][nc] = dist[r][c] + 1  # STEP 6
                max_dist = max(max_dist, dist[nr][nc])  # STEP 6
                queue.append((nr, nc))  # STEP 6

    return max_dist  # STEP 7

📊

As Far from Land as Possible - Watch the Algorithm Execute, Step by Step

Watching the BFS expansion visually clarifies how distances propagate layer by layer, which is hard to grasp from code alone.

Visiting: none

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Visiting: none

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

0,00,22,02,2

Visiting: none

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

0,00,22,02,2

Visiting: 0,0

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

0,22,02,2

Visiting: 0,0

Edge: 0,0 → 1,0

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

0,22,02,2

Visiting: 0,0

Edge: 0,0 → 1,0

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

0,22,02,21,0

Visiting: 0,0

Edge: 0,0 → 0,1

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

0,22,02,21,0

Visiting: 0,0

Edge: 0,0 → 0,1

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

0,22,02,21,00,1

Visiting: none

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

0,22,02,21,00,1

Visiting: 0,2

0,2

1,2

Queue / Stack

2,02,21,00,1

Key Takeaways

✓ BFS from all land cells simultaneously propagates distances layer by layer to water cells.

This simultaneous expansion is hard to visualize from code but clear when watching the queue and node states.

✓ Distance updates only occur for unvisited water cells, ensuring shortest distance from land is recorded.

This prevents revisiting and ensures BFS finds the minimum distance efficiently.

✓ The maximum distance found in the distance matrix after BFS completes is the answer.

Watching the distance values grow stepwise helps understand how BFS finds the farthest water cell.

Practice

1. You are given a town with n people labeled from 1 to n. Some people trust others, represented as pairs [a, b] meaning person a trusts person b. The town judge is defined as someone who trusts nobody but is trusted by everyone else. Which approach guarantees finding the town judge efficiently?

easy

A. Use a single array to track trust scores by incrementing for trusted and decrementing for trusting, then find the person with score n-1.

B. Use a brute force approach checking each person by scanning the entire trust list twice.

C. Use dynamic programming to build a trust matrix and find the person with the highest trust count.

D. Use a greedy approach to pick the person trusted by the most and verify if they trust nobody.

Solution

1. Step 1: Understand the problem constraints

   The town judge trusts nobody and is trusted by everyone else, so their trust score should be exactly n-1.

2. Step 2: Use a single trust score array

   Increment the score for each person trusted and decrement for each person who trusts someone else. The judge will have a score of n-1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with trust score array finds judge efficiently [OK]

Hint: Trust score array captures trust relationships efficiently [OK]

Common Mistakes:

• Assuming greedy max trusted person is always judge
• Using DP unnecessarily
• Brute force is too slow for large inputs

2. You are given a set of rooms, each containing keys to other rooms. Starting from room 0, you want to determine if you can visit every room by collecting keys along the way. Which algorithmic approach guarantees an optimal solution to this problem?

easy

A. Graph traversal using DFS or BFS with a visited set to avoid revisiting rooms

B. Sorting rooms by number of keys and visiting in descending order

C. Dynamic programming to store reachable rooms and combine results

D. Greedy algorithm that picks the room with the most keys first

Solution

1. Step 1: Understand the problem as graph traversal

   The rooms and keys form a directed graph where edges represent keys leading to other rooms.

2. Step 2: Identify the correct algorithmic pattern

   DFS or BFS with a visited set ensures all reachable nodes (rooms) are visited without repetition, guaranteeing correctness and optimality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Graph traversal with visited set is standard for reachability [OK]

Hint: Keys and Rooms is a graph reachability problem [OK]

Common Mistakes:

• Thinking greedy approach works because more keys means more rooms
• Trying DP which is unnecessary and overcomplicates
• Sorting rooms doesn't guarantee connectivity

3. Consider the following BFS-based code snippet for finding the max area of an island in a grid. Given the input grid below, what is the final returned max area?

grid = [
  [0,1,0],
  [1,1,0],
  [0,0,1]
]

from collections import deque

def maxAreaOfIsland(grid):
    rows, cols = len(grid), len(grid[0])
    visited = set()
    max_area = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and (r, c) not in visited:
                queue = deque([(r, c)])
                area = 0
                while queue:
                    row, col = queue.popleft()
                    if (row, col) in visited:
                        continue
                    visited.add((row, col))
                    area += 1
                    for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in visited:
                            queue.append((nr, nc))
                max_area = max(max_area, area)
    return max_area

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace BFS starting at (0,1)

   Queue starts with (0,1). Visit (0,1), area=1. Add neighbors (1,1) and (0,0) is water, (0,2) water, (-1,1) invalid. Next visit (1,1), area=2. Add neighbors (2,1) water, (0,1) visited, (1,2) water, (1,0) land and not visited -> add (1,0). Next visit (1,0), area=3. Add neighbors (2,0) water, (0,0) water, (1,1) visited, (1,-1) invalid.

2. Step 2: BFS ends with area=3 for first island. Next island at (2,2) alone area=1. Max area = max(3,1) = 3

   But note (0,1), (1,1), (1,0) are connected forming area 3.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Largest connected island has 3 cells [OK]

Hint: Trace BFS queue expansions carefully [OK]

Common Mistakes:

• Counting diagonal neighbors
• Double counting visited cells
• Off-by-one in area increment

4. Suppose the problem is modified so that you can only move in 4 directions (up, down, left, right) instead of 8. Which of the following statements about the shortest path algorithm is true?

hard

A. Greedy Best-First Search guarantees shortest path with 4-direction moves

B. Bidirectional BFS still finds the shortest path, but the path length may be longer due to restricted moves

C. DFS with backtracking becomes optimal since fewer directions reduce complexity

D. Dynamic Programming is required to handle the reduced movement directions

Solution

1. Step 1: Understand movement restriction impact

   Reducing to 4 directions limits possible paths, potentially increasing shortest path length.

2. Step 2: Evaluate algorithm suitability

   Bidirectional BFS still finds shortest path efficiently; DFS and greedy do not guarantee shortest path.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bidirectional BFS adapts to movement constraints, still optimal [OK]

Hint: Bidirectional BFS adapts to movement constraints [OK]

Common Mistakes:

• Assuming DFS or greedy become optimal
• Thinking DP is needed for movement changes

5. Suppose the Surrounded Regions problem is modified so that the board can be very large and the number of 'O's connected to the boundary is small. Which of the following modifications to the BFS approach would improve space efficiency without sacrificing correctness?

hard

A. Use DFS with recursion instead of BFS to avoid storing a large queue.

B. Only enqueue boundary 'O's and avoid marking visited cells, relying on board state changes.

C. Use BFS but mark visited cells in-place and prune early when no new 'O's are found.

D. Run BFS from every 'O' cell to ensure all regions are checked independently.

Solution

1. Step 1: Consider space usage of BFS queue

   BFS queue can grow large if many 'O's are connected; marking visited in-place helps avoid revisiting.

2. Step 2: Prune BFS early when no new 'O's are found

   This reduces unnecessary queue growth and improves space efficiency without losing correctness.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   In-place marking plus pruning optimizes BFS space [OK]

Hint: In-place marking and pruning reduce BFS queue size [OK]

Common Mistakes:

• Using DFS recursion can cause stack overflow on large boards.
• Not marking visited cells causes infinite loops or revisits.
• Running BFS from every 'O' is inefficient and unnecessary.