Log inSign up
mediumLeetCodeNot Started

Surrounded Regions

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Surrounded Region Explanation: - An 'O' cell is surrounded if there is no path of 4-directionally adjacent 'O' cells leading from it to the boundary of the board. - Any 'O' on the border of the board is not surrounded, and any 'O' connected to a border 'O' is also not surrounded.

Example 1:

Input: board = [ ["X","X","X","X"], ["X","O","O","X"], ["X","X","O","X"], ["X","O","X","X"] ]
Output: [ ["X","X","X","X"], ["X","X","X","X"], ["X","X","X","X"], ["X","O","X","X"] ]
Explanation: The central cluster of 3 Os is completely enclosed by Xs and gets flipped to X. The bottom O at (3,1) touches the bottom border and survives.

Example 2:

Input: board = [["X"]]
Output: [["X"]]
Explanation: Single cell with X remains unchanged.

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] is X or O

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D Grid Traversal (DFS and BFS)
  • Connected Components in 4-directional matrices
  • Boundary coordinate identification in 2D arrays

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Reverse Flood Fill pattern: initiate graph traversals from boundary seeds inward.
  • Utilize in-place 3-state encoding ('O' -> 'E' -> 'X'/'O') to eliminate auxiliary visited arrays.
  • Formulate grid boundary connectivity using both DFS/BFS and Disjoint Set Union (DSU).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • 2D grid where connected regions enclosed by a perimeter boundary need modification.
  • Boundary-connected elements are immune/exempt from modification.
  • Need to avoid expensive path-reachability queries from all interior cells.

Algorithmic Decision Tree:

  • Invert the problem using Reverse Boundary Flood Fill (DFS/BFS): traverse only the 4 perimeter edges.
  • Temporarily mutate visited safe cells into a third state marker 'E', then run a final single-pass matrix transformation.

Connected Patterns:

Number of Enclaves (LeetCode 1020)Number of Closed Islands (LeetCode 1254)Flood Fill (LeetCode 733)Pacific Atlantic Water Flow

1. Per-Component DFS with Boundary Reachability Flag

Intuition

Isolate each connected component of Os. If no cell in the component touches row 0, m-1 or col 0, n-1, flip all cells in the recorded component to X.

Algorithm

  1. Step 1: Maintain a global visited[m][n] boolean array.
  2. Step 2: Iterate over every cell (r, c). If board[r][c] == O and not visited, start component search.
  3. Step 3: Collect all cells in the connected component and check if any cell lies on the boundary.
  4. Step 4: If touchesBoundary == false, iterate through all cells in the component and flip board[r][c] = X.

Per-Component DFS with Boundary Reachability Flag Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [(1,1):'O', (1,2):'O', (2,2):'O', (3,1):'O']
Current operationSTEP 1 OF 6
Encounter 'O' at (1,1)
Visual state
Values and pointers at this exact step
pointers
S
O
O
O
0
↑ DFS start
1
2
Variables at this step
cell
(1,1)
reachesBoundary
false
Check / comparison
board[1][1] == 'O'
Decision / next transition
Explore connected 'O' component from (1,1).
Why this step matters

Encounter O at (1,1). Launch DFS with reachesBoundary = false.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 int m, n;
6 int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
7
8 void dfs(int r, int c, std::vector<std::vector<char>>& board, std::vector<std::vector<bool>>& visited,
9 std::vector<std::pair<int, int>>& component, bool& touchesBorder) {
10 visited[r][c] = true;
11 component.push_back({r, c});
12
13 if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
14 touchesBorder = true;
15 }
16
17 for (auto& d : dirs) {
18 int nr = r + d[0], nc = c + d[1];
19 if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'O' && !visited[nr][nc]) {
20 dfs(nr, nc, board, visited, component, touchesBorder);
21 }
22 }
23 }
24
25public:
26 void solve(std::vector<std::vector<char>>& board) {
27 if (board.empty() || board[0].empty()) return;
28 m = board.size();
29 n = board[0].size();
30 std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
31
32 for (int r = 0; r < m; ++r) {
33 for (int c = 0; c < n; ++c) {
34 if (board[r][c] == 'O' && !visited[r][c]) {
35 std::vector<std::pair<int, int>> component;
36 bool touchesBorder = false;
37 dfs(r, c, board, visited, component, touchesBorder);
38
39 if (!touchesBorder) {
40 for (auto& cell : component) {
41 board[cell.first][cell.second] = 'X';
42 }
43 }
44 }
45 }
46 }
47 }
48};
49
50int main() {
51 Solution solver;
52 std::vector<std::vector<char>> board = {
53 {'X', 'X', 'X', 'X'},
54 {'X', 'O', 'O', 'X'},
55 {'X', 'X', 'O', 'X'},
56 {'X', 'O', 'X', 'X'}
57 };
58 solver.solve(board);
59 for (const auto& row : board) {
60 for (char c : row) std::cout << c << " ";
61 std::cout << "
62";
63 }
64 return 0;
65}

Time & Space Complexity

  • Time complexity: O(M * N) — Time complexity for Per-Component DFS with Boundary Reachability Flag.
  • Space complexity: O(M * N) — Space complexity for Per-Component DFS with Boundary Reachability Flag.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Disjoint Set Union (Union-Find with Dummy Node)

Intuition

Union-Find groups cells into equivalence classes. Any component that unions with the dummy node is border-connected and immune.

Algorithm

  1. Step 1: Create DSU structure of size M * N + 1. Index M * N is the dummy node.
  2. Step 2: For each cell (r, c) == O: if on boundary, union with dummy node.
  3. Step 3: For each cell (r, c) == O, union with 4-directional adjacent O cells.
  4. Step 4: Traverse matrix: if board[r][c] == O and find(r * n + c) != find(dummy), set board[r][c] = X.

Disjoint Set Union (Union-Find) Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [(1,1):'O', (1,2):'O', (2,2):'O', (3,1):'O', Dummy=Safe]
Current operationSTEP 1 OF 6
Create DSU with MN + 1 nodes
Visual state
Values and pointers at this exact step
pointers
S
SAFE
0
↑ dummy
Variables at this step
dummy
D
totalNodes
17
Check / comparison
Initialize DSU
Decision / next transition
All cells initially in their own set; Dummy node ready.
Why this step matters

Create DSU with M*N + 1 nodes. Dummy node D = M*N represents the Safe Boundary.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class DSU {
5 std::vector<int> parent;
6public:
7 DSU(int n) : parent(n) {
8 for (int i = 0; i < n; ++i) parent[i] = i;
9 }
10 int find(int x) {
11 if (parent[x] == x) return x;
12 return parent[x] = find(parent[x]);
13 }
14 void unite(int x, int y) {
15 int rootX = find(x), rootY = find(y);
16 if (rootX != rootY) parent[rootX] = rootY;
17 }
18 bool connected(int x, int y) {
19 return find(x) == find(y);
20 }
21};
22
23class Solution {
24public:
25 void solve(std::vector<std::vector<char>>& board) {
26 if (board.empty() || board[0].empty()) return;
27 int m = board.size(), n = board[0].size();
28 int dummy = m * n;
29 DSU dsu(dummy + 1);
30
31 for (int r = 0; r < m; ++r) {
32 for (int c = 0; c < n; ++c) {
33 if (board[r][c] == 'O') {
34 int id = r * n + c;
35 if (r == 0 || r == m - 1 || c == 0 || c == n - 1) {
36 dsu.unite(id, dummy);
37 }
38 if (r > 0 && board[r - 1][c] == 'O') dsu.unite(id, (r - 1) * n + c);
39 if (c > 0 && board[r][c - 1] == 'O') dsu.unite(id, r * n + c - 1);
40 }
41 }
42 }
43
44 for (int r = 0; r < m; ++r) {
45 for (int c = 0; c < n; ++c) {
46 if (board[r][c] == 'O' && !dsu.connected(r * n + c, dummy)) {
47 board[r][c] = 'X';
48 }
49 }
50 }
51 }
52};
53
54int main() {
55 Solution solver;
56 std::vector<std::vector<char>> b = {
57 {'X', 'X', 'X', 'X'},
58 {'X', 'O', 'O', 'X'},
59 {'X', 'X', 'O', 'X'},
60 {'X', 'O', 'X', 'X'}
61 };
62 solver.solve(b);
63 for (const auto& row : b) {
64 for (char c : row) std::cout << c << " ";
65 std::cout << "
66";
67 }
68 return 0;
69}

Time & Space Complexity

  • Time complexity: O(M * N * α(M * N)) — Time complexity for Disjoint Set Union (Union-Find with Dummy Node).
  • Space complexity: O(M * N) — Space complexity for Disjoint Set Union (Union-Find with Dummy Node).

3. Boundary Reverse Flood Fill (DFS Marker Method)

Intuition

Instead of searching outward from inside, start from the safe border islands. Anything untouched by the border DFS is enclosed and must be captured.

Algorithm

  1. Step 1: Check edge case if m <= 2 or n <= 2; all Os touch boundary, so nothing can be surrounded.
  2. Step 2: Run DFS from all Os in the first and last rows (r = 0, r = m - 1).
  3. Step 3: Run DFS from all Os in the first and last columns (c = 0, c = n - 1).
  4. Step 4: In the DFS, replace O with temporary character E (Escaped/Safe) and recursively visit 4 unvisited neighbors.
  5. Step 5: Iterate through the whole board: if board[r][c] == O, flip to X; if board[r][c] == E, restore to O.

Boundary Reverse Flood Fill Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [(1,1):'O', (1,2):'O', (2,2):'O', (3,1):'O']
Current operationSTEP 1 OF 6
Key insight: Any 'O' that cannot be captured must connect to a border 'O'
Visual state
Values and pointers at this exact step
pointers
S
O
0
↑ border 'O'
Variables at this step
borderCell
(3,1)
action
dfs_mark
Check / comparison
Border scan: (3,1) == 'O'
Decision / next transition
Launch DFS flood fill from border cell (3,1).
Why this step matters

Key insight: Any O that cannot be captured must connect to a border O. Scan outer borders.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 int m, n;
6 int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
7
8 void dfs(int r, int c, std::vector<std::vector<char>>& board) {
9 board[r][c] = 'E'; // Mark as escaped / immune
10
11 for (auto& d : dirs) {
12 int nr = r + d[0];
13 int nc = c + d[1];
14 if (nr >= 0 && nr < m && nc >= 0 && nc < n && board[nr][nc] == 'O') {
15 dfs(nr, nc, board);
16 }
17 }
18 }
19
20public:
21 void solve(std::vector<std::vector<char>>& board) {
22 if (board.empty() || board[0].empty()) return;
23 m = board.size();
24 n = board[0].size();
25 if (m <= 2 || n <= 2) return; // All cells touch boundary or are isolated
26
27 // 1. Traverse top and bottom boundaries
28 for (int c = 0; c < n; ++c) {
29 if (board[0][c] == 'O') dfs(0, c, board);
30 if (board[m - 1][c] == 'O') dfs(m - 1, c, board);
31 }
32
33 // 2. Traverse left and right boundaries
34 for (int r = 0; r < m; ++r) {
35 if (board[r][0] == 'O') dfs(r, 0, board);
36 if (board[r][n - 1] == 'O') dfs(r, n - 1, board);
37 }
38
39 // 3. Post-process matrix: __SF_TOKEN_A__ -> __SF_TOKEN_B__ (captured), __SF_TOKEN_C__ -> __SF_TOKEN_D__ (restored)
40 for (int r = 0; r < m; ++r) {
41 for (int c = 0; c < n; ++c) {
42 if (board[r][c] == 'O') {
43 board[r][c] = 'X';
44 } else if (board[r][c] == 'E') {
45 board[r][c] = 'O';
46 }
47 }
48 }
49 }
50};
51
52int main() {
53 Solution solver;
54 std::vector<std::vector<char>> board = {
55 {'X', 'X', 'X', 'X'},
56 {'X', 'O', 'O', 'X'},
57 {'X', 'X', 'O', 'X'},
58 {'X', 'O', 'X', 'X'}
59 };
60
61 solver.solve(board);
62 std::cout << "Surrounded Regions Captured Result:
63";
64 for (const auto& row : board) {
65 for (char c : row) std::cout << c << " ";
66 std::cout << "
67";
68 }
69 return 0;
70}

Time & Space Complexity

  • Time complexity: O(M * N) — Time complexity for Boundary Reverse Flood Fill (DFS Marker Method).
  • Space complexity: O(M * N) — Space complexity for Boundary Reverse Flood Fill (DFS Marker Method).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Component DFS with Boundary CheckO(M * N)O(M * N)For every O, find its full connected component and check if any cell touches the border before flipping.Explicit component list storage.
2.Better — Union-Find with Dummy NodeO(M * N * α(M * N))O(M * N)Connect all boundary Os to a dummy node (M*N). Flip all Os that do not share the dummy parent.Union-find path compression operations.
3.Optimal — Boundary Reverse Flood FillOptimalO(M * N)O(M * N) call stackRun DFS only from perimeter Os, marking reachable cells as E. Flip remaining O to X and restore E to O.None; optimal linear scan.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —
  • Edge Case — Input: `, Expected: ` —

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the reverse intuition right away: finding border-connected safe components is much simpler than checking all interior paths.
  2. Discuss both DFS and BFS implementations for border flood fill.
  3. Mention in-place state flag E as an optimal technique to achieve O(1) auxiliary space (aside from recursion call stack).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Surrounded Regions?

2.Why is the brute force approach suboptimal for large inputs in Surrounded Regions?

3.Which data structure or technique enables the optimal solution for Surrounded Regions?

Back to DSA Sheet