Surrounded Regions

▶

Steps

setup

Initialize variables and queue

Initialize board dimensions and create an empty queue to hold boundary 'O's for BFS.

💡 Setting up dimensions and queue prepares for boundary scanning and BFS marking.

Line:

m, n = len(board), len(board[0])
queue = deque()

💡 We need to know board size and have a data structure to track BFS frontier.

setup

Add boundary 'O's from left and right columns

Scan left and right columns for 'O's. Found one at (3,1), mark it safe 'S' and enqueue it.

💡 Boundary 'O's are safe and must be preserved, so we mark and enqueue them first.

Line:

for i in range(m):
    for j in [0, n-1]:
        if board[i][j] == 'O':
            queue.append((i, j))
            board[i][j] = 'S'

💡 Only boundary 'O's start BFS; interior 'O's are not enqueued here.

setup

Add boundary 'O's from top and bottom rows

Scan top and bottom rows for 'O's. None found on top row. On bottom row, (3,1) already processed, no new additions.

💡 We ensure all boundary 'O's are enqueued to start BFS from all safe points.

Line:

for j in range(n):
    for i in [0, m-1]:
        if board[i][j] == 'O':
            queue.append((i, j))
            board[i][j] = 'S'

💡 Boundary scanning complete; BFS queue initialized with all safe 'O's.

traverse

Start BFS: dequeue (3,1) and mark neighbors

Dequeue cell (3,1) from queue to process its neighbors for safe 'O's.

💡 Processing each queued cell expands the safe region by marking connected 'O's.

Line:

x, y = queue.popleft()

💡 We explore neighbors of (3,1) to find connected 'O's to mark safe.

compare

Check neighbor (2,1) of (3,1)

Check cell (2,1) which is 'X', so not safe 'O'. No enqueue or mark.

💡 Only 'O' neighbors are marked safe and enqueued; 'X' neighbors are ignored.

Line:

if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'O':

💡 BFS only expands through 'O' cells.

compare

Check neighbor (4,1) of (3,1) - out of bounds

Neighbor (4,1) is outside board bounds, so ignored.

💡 Boundary checks prevent invalid access during BFS.

Line:

if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'O':

💡 BFS respects board boundaries.

compare

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

Neighbor (3,0) is 'X', so not safe 'O'. No enqueue or mark.

💡 Only 'O' neighbors are enqueued and marked safe.

Line:

if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'O':

💡 BFS does not expand into 'X' cells.

compare

Check neighbor (3,2) of (3,1)

Neighbor (3,2) is 'X', so not safe 'O'. No enqueue or mark.

💡 Only 'O' neighbors are enqueued and marked safe.

Line:

if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'O':

💡 BFS does not expand into 'X' cells.

traverse

Finish processing (3,1), mark done

All neighbors checked, mark (3,1) as done and remove from processing.

💡 Marking done means this cell's safe region expansion is complete.

Line:

while queue:

💡 BFS continues until queue is empty; currently queue is empty.

prune

Flip surrounded 'O's to 'X' and restore safe 'S' to 'O'

Iterate over all cells: flip 'O' to 'X' (surrounded), and 'S' back to 'O' (safe).

💡 This final step completes the solution by updating the board to the output state.

Line:

for i in range(m):
    for j in range(n):
        if board[i][j] == 'O':
            board[i][j] = 'X'
        elif board[i][j] == 'S':
            board[i][j] = 'O'

💡 Only 'O's not connected to boundary remain flipped; safe 'O's restored.

from collections import deque

def solve(board):
    if not board or not board[0]:
        return
    m, n = len(board), len(board[0])  # STEP 1
    queue = deque()  # STEP 1

    # Add boundary 'O's from left and right columns
    for i in range(m):  # STEP 2
        for j in [0, n-1]:
            if board[i][j] == 'O':
                queue.append((i, j))  # STEP 2
                board[i][j] = 'S'  # STEP 2

    # Add boundary 'O's from top and bottom rows
    for j in range(n):  # STEP 3
        for i in [0, m-1]:
            if board[i][j] == 'O':
                queue.append((i, j))  # STEP 3
                board[i][j] = 'S'  # STEP 3

    # BFS to mark safe 'O's
    while queue:  # STEP 4
        x, y = queue.popleft()  # STEP 4
        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:  # STEP 5-8
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and board[nx][ny] == 'O':
                board[nx][ny] = 'S'  # STEP 5-8
                queue.append((nx, ny))  # STEP 5-8

    # Flip surrounded 'O's to 'X' and restore safe 'S' to 'O'
    for i in range(m):  # STEP 10
        for j in range(n):
            if board[i][j] == 'O':
                board[i][j] = 'X'  # STEP 10
            elif board[i][j] == 'S':
                board[i][j] = 'O'  # STEP 10

📊

Surrounded Regions - Watch the Algorithm Execute, Step by Step

Watching the BFS marking and final flipping step-by-step reveals how boundary-connected regions are preserved and surrounded regions are captured.

Visiting: none

0,0

0,1

0,2

0,3

1,0

1,1

1,2

1,3

2,0

2,1

2,2

2,3

3,0

3,1

3,2

3,3

Visiting: none

0,0

0,1

0,2

0,3

1,0

1,1

1,2

1,3

2,0

2,1

2,2

2,3

3,0

3,1

3,2

3,3

Queue / Stack

3,1

Visiting: none

0,0

0,1

0,2

0,3

1,0

1,1

1,2

1,3

2,0

2,1

2,2

2,3

3,0

3,1

3,2

3,3

Queue / Stack

3,1

Visiting: 3,1

3,1

3,0

3,2

2,1

Visiting: 3,1

Edge: 3,1 → 2,1

2,1

3,1

Visiting: 3,1

3,1

Visiting: 3,1

Edge: 3,1 → 3,0

3,0

3,1

Visiting: 3,1

Edge: 3,1 → 3,2

3,2

3,1

Visiting: none

3,1

Visiting: none

0,0

0,1

0,2

0,3

1,0

1,1

1,2

1,3

2,0

2,1

2,2

2,3

3,0

3,1

3,2

3,3

Key Takeaways

✓ Boundary 'O's are the only safe 'O's and must be identified first to preserve them.

It's hard to see from code alone that only boundary-connected 'O's remain unchanged; visualization shows this clearly.

✓ BFS expands from boundary 'O's to mark all connected 'O's as safe, preventing flipping.

Watching BFS queue grow and shrink reveals how safe regions are discovered step-by-step.

✓ After BFS, flipping all unmarked 'O's to 'X' completes the surrounded region capture.

The final iteration over the board is crucial and often overlooked; visualization highlights this final transformation.

Practice

1. You are given a matrix representing heights of cells on a grid. Water can flow from a cell to its neighboring cells if the neighbor's height is less than or equal to the current cell's height. Find all cells from which water can flow to both the top-left and bottom-right edges of the grid. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use dynamic programming to store maximum reachable heights and combine results.

B. Run DFS from every cell to check if it can reach both edges independently.

C. Run BFS or DFS starting from the edges inward, marking reachable cells for each edge, then find their intersection.

D. Apply a greedy approach by always moving to the neighbor with the highest height.

Solution

1. Step 1: Understand flow direction

   Water flows from higher or equal height to lower or equal height neighbors, so starting from edges inward ensures we only visit reachable cells.

2. Step 2: Reverse BFS/DFS from edges

   By running BFS/DFS from the edges inward, we mark all cells that can flow to each ocean, then intersect these sets to find cells that can flow to both.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Starting from edges avoids repeated DFS from every cell [OK]

Hint: Reverse BFS/DFS from edges is optimal [OK]

Common Mistakes:

• Thinking BFS/DFS must start from each cell
• Using greedy approach fails on plateaus

2. Consider the following buggy code for finding the cheapest flight within K stops. Which line contains the subtle bug that can cause incorrect results?

from collections import defaultdict
import heapq

def findCheapestPrice(n, flights, src, dst, K):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))
    heap = [(0, src, 0)]  # cost, node, stops
    while heap:
        cost, node, stops = heapq.heappop(heap)
        if node == dst:
            return cost
        if stops < K:  # BUG: should be stops <= K
            for nei, price in graph[node]:
                heapq.heappush(heap, (cost + price, nei, stops + 1))
    return -1

medium

A. Line with condition if stops < K:

B. Line initializing the heap with (0, src, 0)

C. Line checking if node == dst

D. Line pushing neighbors into the heap

Solution

1. Step 1: Understand stops constraint

   The problem allows up to K stops, meaning stops can be equal to K, not strictly less.

2. Step 2: Identify bug

   The condition 'if stops < K:' excludes paths with exactly K stops, missing valid solutions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to 'stops <= K' fixes the bug [OK]

Hint: Stops ≤ K allows exactly K stops, not less [OK]

Common Mistakes:

• Using stops < K instead of stops <= K
• Ignoring stops count in pruning
• Returning early without checking stops

3. Consider the following buggy code snippet from the BFS approach for Pacific Atlantic Water Flow. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line that appends (0, j) to pacific_queue

B. Missing line that sets atlantic_reachable[m-1][j] = True

C. Line that sets pacific_reachable[0][j] = True

D. Line that appends (m-1, j) to atlantic_queue

Solution

1. Step 1: Check border initialization

   Both oceans' reachable arrays must mark all border cells as True initially.

2. Step 2: Identify missing marking

   For atlantic ocean, bottom row cells (m-1, j) are added to queue but not marked reachable, causing BFS to miss them.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing atlantic_reachable[m-1][j] = True causes incomplete results [OK]

Hint: All border cells must be marked reachable initially [OK]

Common Mistakes:

• Forgetting to mark atlantic_reachable bottom row
• Marking visited after BFS causes infinite loops

4. What is the time complexity of the optimal Dijkstra's algorithm variant solution for the minimum effort path problem on an n x m grid?

medium

A. O(n * m^2)

B. O(n * m * log(n * m))

C. O((n * m)^2)

D. O(n * m)

Solution

1. Step 1: Identify graph size

   The grid has n*m nodes and up to 4 edges per node, so edges E = O(n*m).

2. Step 2: Analyze Dijkstra's complexity

   Using a min-heap, each node is pushed/popped at most once, heap operations cost O(log(n*m)), total O(n*m*log(n*m)).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Log factor comes from heap operations on n*m nodes [OK]

Hint: Dijkstra on grid -> O(V log V) with V=n*m [OK]

Common Mistakes:

• Confusing edges with nodes count
• Assuming O(n*m^2) due to nested loops
• Ignoring log factor from heap

5. Suppose the problem changes: now flights can be reused multiple times (cycles allowed), but you still want the cheapest price within K stops. Which modification to the algorithm is necessary to handle this correctly? A) Use Bellman-Ford with K+1 iterations to relax edges repeatedly. B) Use the same Dijkstra approach without changes since it handles cycles. C) Use DFS with memoization to avoid infinite loops. D) Use BFS without tracking stops because cycles are allowed.

hard

A. Use Bellman-Ford with K+1 iterations to relax edges repeatedly.

B. Use the same Dijkstra approach without changes since it handles cycles.

C. Use DFS with memoization to avoid infinite loops.

D. Use BFS without tracking stops because cycles are allowed.

Solution

1. Step 1: Understand reuse and cycles

   Allowing reuse means cycles can exist, so Dijkstra's assumption of no negative cycles and no repeated nodes fails.

2. Step 2: Identify suitable algorithm

   Bellman-Ford can handle cycles by relaxing edges up to K+1 times, correctly computing shortest paths with stop constraints.

3. Step 3: Why other options fail

   Dijkstra without changes may loop infinitely or miss valid paths; DFS risks stack overflow; BFS without stops tracking ignores constraints.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Bellman-Ford handles cycles with controlled relaxations [OK]

Hint: Bellman-Ford handles cycles with limited relaxations [OK]

Common Mistakes:

• Assuming Dijkstra works with cycles
• Ignoring stops tracking in BFS
• Using DFS without pruning leads to infinite recursion