Surrounded Regions

📋

Problem

Imagine a map of lakes and land where lakes completely enclosed by land need to be drained. How do you identify which lakes are truly enclosed?

Given an m x n matrix board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. An 'O' region is considered surrounded if it is not connected to any 'O' on the boundary of the board.

1 ≤ m, n ≤ 200board[i][j] is 'X' or 'O'

Edge cases: All 'O's on the boundary → no flipsSingle cell board with 'O' → no flipsBoard with no 'O's → no changes

</>

IDE

def solve(board: list[list[str]]) -> None:public void solve(char[][] board)void solve(vector<vector<char>>& board)function solve(board)

def solve(board):
    # Write your solution here
    pass

class Solution {
    public void solve(char[][] board) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void solve(vector<vector<char>>& board) {
    // Write your solution here
}

function solve(board) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']]Flipped no 'O's at all, missing surrounded region flips.✅ Implement BFS/DFS from boundary 'O's to mark safe regions, then flip unmarked 'O's.

Wrong: [['O','X','O','X','O'],['X','O','O','X','O'],['X','O','X','O','X'],['O','X','O','O','O'],['X','X','O','X','O']]Flipped no 'O's in complex board, missing surrounded region flips.✅ Mark boundary-connected 'O's first, then flip only surrounded 'O's.

Wrong: Code crashes or returns empty on empty input.✅ Add early return if board is empty or board[0] is empty.

Wrong: XFlipped single boundary 'O' incorrectly.✅ Treat boundary cells as protected; do not flip boundary 'O's.

Wrong: [['X','X','X'],['X','X','X'],['X','X','X']]Flipped all 'O's including boundary-connected ones due to greedy or diagonal adjacency errors.✅ Use BFS/DFS with 4-directional adjacency from boundary to mark safe 'O's.

✓

Test Cases

Try testing your code on empty and minimal boards to catch base case bugs.

Consider tricky patterns that might fool greedy or incorrect adjacency logic.

Prepare for large inputs that require efficient O(m*n) BFS/DFS solutions.

t1_01basic

Input{"board":[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]}

Expectednull

⏱ Performance - must finish in 2000ms

The 'O's in the middle are surrounded by 'X' and flipped, but the 'O' connected to the boundary remains.

💡 Think about marking 'O's connected to the boundary first.

💡 Use DFS or BFS to find all 'O's connected to the edges and protect them.

💡 Flip all unmarked 'O's to 'X' after marking boundary-connected ones.

Why it failed: Failed to protect boundary-connected 'O's; likely flipped all 'O's indiscriminately. Fix by marking boundary-connected 'O's before flipping.

✓ Correctly identifies and preserves boundary-connected 'O's while flipping surrounded regions.

t1_02basic

Input{"board":[["O","X","X","O","X"],["X","X","X","X","O"],["X","X","X","O","X"],["O","X","O","O","O"],["X","X","O","X","O"]]}

Expectednull

⏱ Performance - must finish in 2000ms

Only 'O's not connected to boundary are flipped; boundary-connected 'O's remain.

💡 Check which 'O's are reachable from the boundary.

💡 Mark these reachable 'O's to avoid flipping.

💡 Flip all other 'O's to 'X' after marking.

Why it failed: Incorrectly flipped 'O's connected to boundary or missed flipping surrounded 'O's. Fix by BFS/DFS from boundary 'O's and flip only unmarked ones.

✓ Successfully flips only surrounded 'O's while preserving boundary-connected ones.

t2_01edge

Input{"board":[]}

Expectednull

⏱ Performance - must finish in 2000ms

Empty board input should remain unchanged.

💡 Handle empty input gracefully.

💡 Check if board or board[0] is empty before processing.

💡 Return immediately if board is empty to avoid errors.

Why it failed: Code crashes or errors on empty input due to missing checks. Fix by adding early return if board is empty or board[0] is empty.

✓ Correctly handles empty board without errors.

t2_02edge

Input{"board":[["O"]]}

Expectednull

⏱ Performance - must finish in 2000ms

Single cell 'O' on boundary should not be flipped.

💡 Single cell is always on boundary.

💡 Boundary 'O's should never be flipped.

💡 Ensure boundary checks include single cell cases.

Why it failed: Flipped single boundary 'O' incorrectly. Fix by treating boundary cells as protected.

✓ Preserves single boundary 'O' correctly.

t2_03edge

Input{"board":[["X","X","X"],["X","X","X"],["X","X","X"]]}

Expectednull

⏱ Performance - must finish in 2000ms

Board with no 'O's remains unchanged.

💡 If no 'O's, no flips needed.

💡 Check if your code unnecessarily modifies 'X's.

💡 Return original board if no 'O's found.

Why it failed: Modified board with no 'O's or caused errors. Fix by processing only 'O's and leaving 'X's untouched.

✓ Leaves board with no 'O's unchanged.

t3_01corner

Input{"board":[["O","O","O","O"],["O","O","O","O"],["O","O","O","O"],["O","O","O","O"]]}

Expectednull

⏱ Performance - must finish in 2000ms

All 'O's are boundary-connected, so none should be flipped.

💡 Check if your code flips all 'O's regardless of boundary connection.

💡 Mark all boundary 'O's and their connected 'O's before flipping.

💡 Avoid flipping any 'O' reachable from boundary.

Why it failed: Flipped all 'O's including boundary-connected ones. Fix by BFS/DFS from boundary and only flip unmarked 'O's.

✓ Correctly preserves all boundary-connected 'O's.

t3_02corner

Input{"board":[["X","O","X","O","X"],["O","X","X","X","O"],["X","X","X","X","X"],["O","X","X","X","O"],["X","O","X","O","X"]]}

Expectednull

⏱ Performance - must finish in 2000ms

Inner 'O's not connected to boundary are flipped; boundary-connected 'O's remain.

💡 Beware of greedy flipping from top-left to bottom-right.

💡 Use BFS/DFS from boundary to mark safe 'O's first.

💡 Flip only unmarked 'O's after marking.

Why it failed: Greedy approach flips some boundary-connected 'O's or misses some surrounded 'O's. Fix by BFS/DFS from boundary and flip unmarked only.

✓ Correctly flips only surrounded 'O's, preserving boundary-connected ones.

t3_03corner

Input{"board":[["X","O","X"],["O","O","O"],["X","O","X"]]}

Expectednull

⏱ Performance - must finish in 2000ms

Center 'O's connected to boundary 'O's should not be flipped.

💡 Check if your code treats diagonal connections as adjacency (they are not).

💡 Only consider up/down/left/right neighbors for connectivity.

💡 Mark boundary-connected 'O's using 4-directional BFS/DFS.

Why it failed: Incorrectly flips 'O's connected diagonally to boundary 'O's. Fix by using only 4-directional adjacency in BFS/DFS.

✓ Correctly preserves 'O's connected orthogonally to boundary.

t4_01performance

Input{"board":[["O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X"],["X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O"],["O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X"],["X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O"],["O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X"],["X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O"],["O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X"],["X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O"],["O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X"],["X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O"],["O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X"],["X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O"],["O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X"],["X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O"],["O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X"],["X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O"],["O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X"],["X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O"],["O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X"],["X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O","X","O"]]}

Expectednull

⏱ Performance - must finish in 2000ms

Large 20x20 board with alternating 'O' and 'X' to test O(m*n) complexity within 2 seconds.

💡 Use BFS/DFS from boundary to mark safe 'O's efficiently.

💡 Avoid repeated scanning of the entire board for each 'O'.

💡 Optimal solution runs in O(m*n) time using boundary marking.

Why it failed: Solution times out due to O(m*n*(m+n)) brute force approach. Fix by using BFS/DFS from boundary to mark connected 'O's first.

✓ Solution runs within time limit using O(m*n) BFS/DFS boundary marking.

Practice

1. Consider the following Python code implementing the Number of Islands problem using in-place DFS. Given the input grid below, what is the final returned value of numIslands(grid)?

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

easy

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Trace DFS calls starting from (0,0)

   DFS marks (0,0), (0,1), and (1,1) as visited, sinking one island.

2. Step 2: Identify remaining islands

   Next unvisited '1' is at (2,0) (second island), then at (2,2) (third island). Total islands counted = 3.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Counting connected components by DFS yields 3 islands [OK]

Hint: Count connected components by DFS marking visited [OK]

Common Mistakes:

• Off-by-one counting islands
• Missing diagonal connections (which don't count)

2. Given the following DFS-based code for rotting oranges, what is the value of max_time after processing the grid [[2,1,1],[1,1,0],[0,1,1]]?

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    time_grid = [[-1]*cols for _ in range(rows)]
    max_time = 0

    def dfs(r, c, time):
        nonlocal max_time
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == 0:
            return
        if time_grid[r][c] != -1 and time_grid[r][c] <= time:
            return
        time_grid[r][c] = time
        max_time = max(max_time, time)
        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 1 or (grid[nr][nc] == 2 and time_grid[nr][nc] > time + 1):
                    dfs(nr, nc, time + 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                dfs(r, c, 0)
    return max_time

easy

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace DFS from rotten orange at (0,0) with time=0

   It rots adjacent fresh oranges incrementally, updating time_grid and max_time as rot spreads.

2. Step 2: Follow rot spread minute by minute

   Rot spreads to (0,1) and (1,0) at time=1, then to (0,2), (1,1), and (2,1) at time=2, and finally to (2,2) at time=3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Maximum rot time matches the longest path from initial rotten orange [OK]

Hint: Max time equals longest rot spread path [OK]

Common Mistakes:

• Off-by-one counting minutes
• Ignoring multiple rotten sources
• Confusing grid indices

3. Consider the following Python code implementing bidirectional BFS to find the shortest path in a binary matrix. Given the input grid below, what is the returned shortest path length?

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

# Code snippet uses the bidirectional BFS approach as described.

What is the output of shortestPathBinaryMatrix(grid)?

easy

A. 3

B. 5

C. -1

D. 4

Solution

1. Step 1: Trace BFS from start (0,0)

   Start at (0,0) with distance 1. Neighbors reachable: (1,1) at distance 2.

2. Step 2: Trace BFS from end (2,2)

   Start at (2,2) with distance 1. Neighbors reachable: (1,2) at distance 2, (1,1) at distance 2.

3. Step 3: Meeting point

   Both searches meet at (1,1). Sum distances: 2 (start side) + 2 (end side) = 4, but since both include the meeting cell, shortest path length is 3.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Shortest path length is 3 steps [OK]

Hint: Bidirectional BFS meets in middle, sum distances minus 1 [OK]

Common Mistakes:

• Off-by-one in path length
• Ignoring meeting cell counted twice

4. What is the time complexity of the optimal algorithm that finds the minimum number of vertices to reach all nodes in a directed acyclic graph with n nodes and e edges?

medium

A. O(n * e) because each node is processed for all edges

B. O(n + e) because each node and edge is processed once

C. O(n^2) because of nested loops over nodes

D. O(e log n) due to priority queue operations in topological sort

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm iterates over all edges once to build the graph and in-degree array, then processes each node and its edges once during the queue processing.

2. Step 2: Combine complexities

   Building graph: O(e), processing nodes and edges in BFS: O(n + e). No nested loops over all nodes and edges.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time in nodes and edges for DAG traversal [OK]

Hint: Topological sort runs in O(n + e) time [OK]

Common Mistakes:

• Assuming nested loops cause O(n*e)
• Confusing with dense graph complexities
• Thinking priority queues are used

5. Suppose the Word Ladder problem is modified so that words can be reused multiple times in the transformation sequence. Which of the following changes to the bidirectional BFS algorithm is necessary to correctly handle this variant?

hard

A. Allow revisiting words but track path length to avoid infinite loops

B. Remove the visited set entirely to allow revisiting words

C. Use a priority queue to prioritize words closer to the endWord

D. Keep visited sets but reset them after each level expansion

Solution

1. Step 1: Understand impact of allowing word reuse

   Allowing reuse means cycles can form, so simply removing visited causes infinite loops.

2. Step 2: Modify algorithm to track path length and avoid infinite loops

   We must allow revisits but prevent infinite cycles by tracking path length or depth limits.

3. Step 3: Why other options fail

   Removing visited causes infinite loops; resetting visited loses progress; priority queue is unrelated to reuse handling.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking path length prevents infinite loops with reuse [OK]

Hint: Allow reuse -> track path length to avoid cycles [OK]

Common Mistakes:

• Removing visited causes infinite loops
• Resetting visited loses pruning
• Using priority queue doesn't solve reuse