Introduction to the Surrounded Regions Problem
The Surrounded Regions problem is a classic graph traversal challenge frequently encountered in coding interviews and competitive programming. Given a 2D board containing the characters 'X' and 'O', the goal is to capture every region of 'O's that is fully surrounded by 'X's on all four sides. Capturing a region means flipping all its 'O' characters into 'X' characters.
However, there is an important exception: any 'O' that lies on the border of the board, or any 'O' connected to a border 'O' through a path of adjacent 'O's, is not considered surrounded and must remain unchanged.
Problem Statement
Formally, you are given an m x n matrix board containing 'X' and 'O'. You must modify the board in place such that:
- Any
'O'that is not connected to the border remains'O'only if it is part of a region fully enclosed by'X'. Otherwise, it gets flipped to'X'. - Any
'O'connected directly or indirectly to a border'O'stays as'O'.
Connectivity is defined in the four cardinal directions: up, down, left, and right.
Why It Matters
This problem is more than an academic exercise. It tests your understanding of several fundamental computer science concepts:
- Graph traversal algorithms — Both Depth-First Search (DFS) and Breadth-First Search (BFS) are applicable, and the problem gives you a chance to compare their trade-offs.
- In-place matrix manipulation — The requirement to modify the board without allocating a duplicate structure encourages efficient memory usage.
- Boundary analysis — Recognizing that border-connected regions are the exception is the key insight that unlocks the solution.
- Recursion and stack management — In languages like Go, deep recursion on large boards can cause stack overflows, making this a great case study for when to prefer iterative approaches.
In real-world scenarios, similar algorithms appear in image processing (flood fill), game development (territory capture games like Go), and geographic information systems where connected regions must be identified and transformed.
Approach and Algorithm
The naive approach — iterating over every 'O' and checking whether it is surrounded — would be inefficient and error-prone. Instead, the optimal strategy inverts the problem: rather than finding surrounded regions, we identify the regions that are not surrounded and protect them.
The Key Insight
Any 'O' that is surrounded must be entirely enclosed by 'X's. This means it cannot reach the border of the board through a path of 'O's. Conversely, any 'O' that can reach the border is not surrounded. Therefore, the algorithm proceeds in three phases:
- Phase 1: Mark border-connected regions. Traverse the borders of the board. Whenever you find an
'O', perform a DFS or BFS to mark every'O'connected to it with a temporary marker, such as'T'. - Phase 2: Capture surrounded regions. Iterate over the entire board. Flip every remaining
'O'to'X'because it was not reached from the border and is therefore surrounded. - Phase 3: Restore marked regions. Flip every
'T'back to'O'to restore the border-connected regions.
This approach runs in O(m × n) time and uses O(m × n) space in the worst case for the recursion or queue, which is optimal for this problem.
Implementation in Go: DFS Solution
Let us implement the DFS-based solution first. We will define a helper function that recursively marks all border-connected 'O's, then apply the three-phase algorithm described above.
package main
import "fmt"
func solve(board [][]byte) {
if len(board) == 0 {
return
}
rows := len(board)
cols := len(board[0])
// Phase 1: Mark border-connected 'O's with 'T'
for r := 0; r < rows; r++ {
if board[r][0] == 'O' {
dfs(board, r, 0, rows, cols)
}
if board[r][cols-1] == 'O' {
dfs(board, r, cols-1, rows, cols)
}
}
for c := 0; c < cols; c++ {
if board[0][c] == 'O' {
dfs(board, 0, c, rows, cols)
}
if board[rows-1][c] == 'O' {
dfs(board, rows-1, c, rows, cols)
}
}
// Phase 2 and 3: Flip 'O' to 'X', restore 'T' to 'O'
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if board[r][c] == 'O' {
board[r][c] = 'X'
} else if board[r][c] == 'T' {
board[r][c] = 'O'
}
}
}
}
func dfs(board [][]byte, r, c, rows, cols int) {
if r < 0 || r >= rows || c < 0 || c >= cols {
return
}
if board[r][c] != 'O' {
return
}
board[r][c] = 'T'
dfs(board, r+1, c, rows, cols)
dfs(board, r-1, c, rows, cols)
dfs(board, r, c+1, rows, cols)
dfs(board, r, c-1, rows, cols)
}
func main() {
board := [][]byte{
{'X', 'X', 'X', 'X'},
{'X', 'O', 'O', 'X'},
{'X', 'X', 'O', 'X'},
{'X', 'O', 'X', 'X'},
}
fmt.Println("Before:")
printBoard(board)
solve(board)
fmt.Println("After:")
printBoard(board)
}
func printBoard(board [][]byte) {
for _, row := range board {
fmt.Println(string(row))
}
fmt.Println()
}
When you run this program, the board in the main function contains a surrounded region of 'O's in the middle and a single 'O' at position (3, 1) that is connected to the bottom border. After running solve, the surrounded 'O's are flipped to 'X', while the border-connected 'O' remains unchanged.
Implementation in Go: BFS Solution
While the DFS solution is elegant and concise, it has a potential drawback: on very large boards, the recursion depth can exceed Go's stack limits, causing a stack overflow panic. The BFS approach avoids this issue entirely by using an explicit queue instead of the call stack.
package main
import "fmt"
type Cell struct {
r, c int
}
func solveBFS(board [][]byte) {
if len(board) == 0 {
return
}
rows := len(board)
cols := len(board[0])
// Collect all border 'O' cells as starting points
queue := []Cell{}
for r := 0; r < rows; r++ {
if board[r][0] == 'O' {
queue = append(queue, Cell{r, 0})
}
if board[r][cols-1] == 'O' {
queue = append(queue, Cell{r, cols - 1})
}
}
for c := 0; c < cols; c++ {
if board[0][c] == 'O' {
queue = append(queue, Cell{0, c})
}
if board[rows-1][c] == 'O' {
queue = append(queue, Cell{rows - 1, c})
}
}
// BFS to mark all border-connected 'O's
directions := []Cell{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for len(queue) > 0 {
cell := queue[0]
queue = queue[1:]
if cell.r < 0 || cell.r >= rows || cell.c < 0 || cell.c >= cols {
continue
}
if board[cell.r][cell.c] != 'O' {
continue
}
board[cell.r][cell.c] = 'T'
for _, d := range directions {
nr := cell.r + d.r
nc := cell.c + d.c
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] == 'O' {
queue = append(queue, Cell{nr, nc})
}
}
}
// Flip remaining 'O' to 'X', restore 'T' to 'O'
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if board[r][c] == 'O' {
board[r][c] = 'X'
} else if board[r][c] == 'T' {
board[r][c] = 'O'
}
}
}
}
func main() {
board := [][]byte{
{'X', 'O', 'X', 'O', 'X', 'O'},
{'O', 'X', 'O', 'X', 'O', 'X'},
{'X', 'O', 'X', 'O', 'X', 'O'},
{'O', 'X', 'O', 'X', 'O', 'X'},
}
fmt.Println("Before:")
for _, row := range board {
fmt.Println(string(row))
}
solveBFS(board)
fmt.Println("\nAfter:")
for _, row := range board {
fmt.Println(string(row))
}
}
In this BFS version, we first collect all border 'O' cells into a queue, then process them level by level. Each 'O' encountered is marked as 'T', and its unvisited 'O' neighbors are added to the queue. This guarantees that we never recurse deeply, making the solution safe for boards of any size.
Testing the Solution
Robust testing is essential to verify correctness. Below is a test file using Go's built-in testing package that covers several edge cases.
package main
import (
"reflect"
"testing"
)
func TestSolve(t *testing.T) {
tests := []struct {
name string
input [][]byte
expected [][]byte
}{
{
name: "empty board",
input: [][]byte{},
expected: [][]byte{},
},
{
name: "single element O",
input: [][]byte{{'O'}},
expected: [][]byte{{'O'}},
},
{
name: "all X",
input: [][]byte{
{'X', 'X'},
{'X', 'X'},
},
expected: [][]byte{
{'X', 'X'},
{'X', 'X'},
},
},
{
name: "surrounded region in center",
input: [][]byte{
{'X', 'X', 'X', 'X'},
{'X', 'O', 'O', 'X'},
{'X', 'X', 'O', 'X'},
{'X', 'O', 'X', 'X'},
},
expected: [][]byte{
{'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X'},
},
},
{
name: "border O stays",
input: [][]byte{
{'O', 'O', 'O'},
{'O', 'X', 'O'},
{'O', 'O', 'O'},
},
expected: [][]byte{
{'O', 'O', 'O'},
{'O', 'X', 'O'},
{'O', 'O', 'O'},
},
},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
// Make a deep copy to avoid mutating test data
input := make([][]byte, len(tt.input))
for i := range tt.input {
input[i] = make([]byte, len(tt.input[i]))
copy(input[i], tt.input[i])
}
solve(input)
if !reflect.DeepEqual(input, tt.expected) {
t.Errorf("got %v, want %v", input, tt.expected)
}
})
}
}
Run the tests with go test -v. These cases cover the empty board, a single border element, a fully enclosed region, and a board where all 'O's are on the border. Adding these tests ensures that both the DFS and BFS implementations behave identically across edge cases.
Best Practices
When implementing the Surrounded Regions solution in Go, keep the following best practices in mind:
- Prefer BFS for large inputs. Go does not perform tail-call optimization, so deeply recursive DFS can panic on boards with long chains of
'O's. If you know the input can be large, use the BFS approach or convert DFS to an iterative version with an explicit stack. - Always check for empty boards. Guard against zero-length boards and zero-length rows at the top of your function to avoid index-out-of-range panics.
- Use a temporary marker wisely. The
'T'marker trick allows in-place modification without extra memory for a visited set. Just make sure the marker does not collide with valid input characters. - Avoid duplicate border processing. When collecting border cells, corners will be checked twice (once by the row loop and once by the column loop). This is harmless because the visited check prevents reprocessing, but be aware of it for performance-sensitive contexts.
- Write table-driven tests. Go's testing framework excels at table-driven tests. Cover edge cases like single-cell boards, all-
'X'boards, all-'O'boards, and boards with complex internal regions. - Consider memory optimization. If you cannot use a temporary marker (for example, if the board might contain
'T'in valid input), use a separate boolean visited matrix or a map. This trades memory for correctness guarantees. - Profile before optimizing. Both DFS and BFS run in
O(m × n)time. Unless profiling reveals a bottleneck, prioritize code clarity over micro-optimizations like avoiding function calls or using bit manipulation.
Conclusion
The Surrounded Regions problem is an excellent exercise in graph traversal, boundary analysis, and in-place matrix manipulation. By flipping the problem on its head — marking the unsurrounded regions first and then capturing everything else — you arrive at a clean, efficient O(m × n) solution. Whether you choose the recursive DFS approach for its elegance or the iterative BFS approach for its safety on large inputs, the core algorithm remains the same. With the implementations, tests, and best practices covered in this guide, you now have everything you need to solve this problem confidently in Go and to adapt the underlying techniques to similar flood-fill and connected-components challenges you may encounter in the future.