Surrounded Regions

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.

Examples

Example 1:

1
2
3
4

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

1
2
3
4

X X X X
X X X X
X X X X
X O X X

1
2
3
4

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: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Solution

This problem is similar to Number of Islands.

Method 1 – Depth-First Search (DFS)

Intuition

The only ‘O’s that cannot be captured are those connected to the border. By marking all border-connected ‘O’s (using DFS), we can safely flip the rest to ‘X’.

Approach

  1. Traverse the border cells and run DFS for every ‘O’ found, marking them (e.g., as ‘#’).
  2. After marking, iterate through the board:
    • Flip all remaining ‘O’s to ‘X’ (these are surrounded).
    • Convert all ‘#’ back to ‘O’ (these are safe).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <vector>
using namespace std;
class Solution {
public:
	void solve(vector<vector<char>>& board) {
		int m = board.size(), n = m ? board[0].size() : 0;
		if (!m || !n) return;
		auto dfs = [&](int i, int j, auto&& dfs_ref) -> void {
			if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;
			board[i][j] = '#';
			dfs_ref(i-1, j, dfs_ref); dfs_ref(i+1, j, dfs_ref);
			dfs_ref(i, j-1, dfs_ref); dfs_ref(i, j+1, dfs_ref);
		};
		for (int i = 0; i < m; ++i) {
			if (board[i][0] == 'O') dfs(i, 0, dfs);
			if (board[i][n-1] == 'O') dfs(i, n-1, dfs);
		}
		for (int j = 0; j < n; ++j) {
			if (board[0][j] == 'O') dfs(0, j, dfs);
			if (board[m-1][j] == 'O') dfs(m-1, j, dfs);
		}
		for (int i = 0; i < m; ++i)
			for (int j = 0; j < n; ++j)
				if (board[i][j] == 'O') board[i][j] = 'X';
				else if (board[i][j] == '#') board[i][j] = 'O';
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func solve(board [][]byte) {
	m, n := len(board), len(board[0])
	var dfs func(i, j int)
	dfs = func(i, j int) {
		if i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O' { return }
		board[i][j] = '#'
		dfs(i-1, j); dfs(i+1, j); dfs(i, j-1); dfs(i, j+1)
	}
	for i := 0; i < m; i++ {
		if board[i][0] == 'O' { dfs(i, 0) }
		if board[i][n-1] == 'O' { dfs(i, n-1) }
	}
	for j := 0; j < n; j++ {
		if board[0][j] == 'O' { dfs(0, j) }
		if board[m-1][j] == 'O' { dfs(m-1, j) }
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == 'O' { board[i][j] = 'X' }
			if board[i][j] == '#' { board[i][j] = 'O' }
		}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
	public void solve(char[][] board) {
		if (board == null || board.length == 0) return;
		int m = board.length, n = board[0].length;
		for (int i = 0; i < m; i++) {
			if (board[i][0] == 'O') merge(board, i, 0);
			if (board[i][n-1] == 'O') merge(board, i, n-1);
		}
		for (int j = 0; j < n; j++) {
			if (board[0][j] == 'O') merge(board, 0, j);
			if (board[m-1][j] == 'O') merge(board, m-1, j);
		}
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
				if (board[i][j] == 'O') board[i][j] = 'X';
				else if (board[i][j] == '#') board[i][j] = 'O';
	}
	private void merge(char[][] board, int i, int j) {
		if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return;
		if (board[i][j] != 'O') return;
		board[i][j] = '#';
		merge(board, i-1, j); merge(board, i+1, j);
		merge(board, i, j-1); merge(board, i, j+1);
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
	fun solve(board: Array<CharArray>) {
		val m = board.size; val n = board[0].size
		fun dfs(i: Int, j: Int) {
			if (i !in 0 until m || j !in 0 until n || board[i][j] != 'O') return
			board[i][j] = '#'
			dfs(i-1, j); dfs(i+1, j); dfs(i, j-1); dfs(i, j+1)
		}
		for (i in 0 until m) {
			if (board[i][0] == 'O') dfs(i, 0)
			if (board[i][n-1] == 'O') dfs(i, n-1)
		}
		for (j in 0 until n) {
			if (board[0][j] == 'O') dfs(0, j)
			if (board[m-1][j] == 'O') dfs(m-1, j)
		}
		for (i in 0 until m)
			for (j in 0 until n)
				when (board[i][j]) {
					'O' -> board[i][j] = 'X'
					'#' -> board[i][j] = 'O'
				}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
	def solve(self, board: list[list[str]]) -> None:
		if not board: return
		m, n = len(board), len(board[0])
		def dfs(i, j):
			if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O': return
			board[i][j] = '#'
			dfs(i-1, j); dfs(i+1, j); dfs(i, j-1); dfs(i, j+1)
		for i in range(m):
			if board[i][0] == 'O': dfs(i, 0)
			if board[i][n-1] == 'O': dfs(i, n-1)
		for j in range(n):
			if board[0][j] == 'O': dfs(0, j)
			if board[m-1][j] == 'O': dfs(m-1, j)
		for i in range(m):
			for j in range(n):
				if board[i][j] == 'O': board[i][j] = 'X'
				elif board[i][j] == '#': board[i][j] = 'O'
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
	pub fn solve(board: &mut Vec<Vec<char>>) {
		let m = board.len();
		let n = if m > 0 { board[0].len() } else { 0 };
		fn dfs(board: &mut Vec<Vec<char>>, i: isize, j: isize, m: usize, n: usize) {
			if i < 0 || i >= m as isize || j < 0 || j >= n as isize || board[i as usize][j as usize] != 'O' { return; }
			board[i as usize][j as usize] = '#';
			dfs(board, i-1, j, m, n); dfs(board, i+1, j, m, n);
			dfs(board, i, j-1, m, n); dfs(board, i, j+1, m, n);
		}
		for i in 0..m {
			if board[i][0] == 'O' { dfs(board, i as isize, 0, m, n); }
			if board[i][n-1] == 'O' { dfs(board, i as isize, (n-1) as isize, m, n); }
		}
		for j in 0..n {
			if board[0][j] == 'O' { dfs(board, 0, j as isize, m, n); }
			if board[m-1][j] == 'O' { dfs(board, (m-1) as isize, j as isize, m, n); }
		}
		for i in 0..m {
			for j in 0..n {
				if board[i][j] == 'O' { board[i][j] = 'X'; }
				else if board[i][j] == '#' { board[i][j] = 'O'; }
			}
		}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

function solve(board: string[][]): void {
	const m = board.length, n = board[0].length;
	function dfs(i: number, j: number) {
		if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] !== 'O') return;
		board[i][j] = '#';
		dfs(i-1, j); dfs(i+1, j); dfs(i, j-1); dfs(i, j+1);
	}
	for (let i = 0; i < m; i++) {
		if (board[i][0] === 'O') dfs(i, 0);
		if (board[i][n-1] === 'O') dfs(i, n-1);
	}
	for (let j = 0; j < n; j++) {
		if (board[0][j] === 'O') dfs(0, j);
		if (board[m-1][j] === 'O') dfs(m-1, j);
	}
	for (let i = 0; i < m; i++)
		for (let j = 0; j < n; j++)
			if (board[i][j] === 'O') board[i][j] = 'X';
			else if (board[i][j] === '#') board[i][j] = 'O';
}

Complexity

  • ⏰ Time complexity: O(mn) where m and n are the board’s dimensions (each cell is visited at most once).
  • 🧺 Space complexity: O(mn) in the worst case for the recursion stack (all ‘O’s on the border).

Method 2 – Breadth-First Search (BFS)

Intuition

Instead of using recursion, we can use a queue to mark all ‘O’s connected to the border. This avoids stack overflow and is more robust for large boards.

Approach

  1. For each border cell, if it is ‘O’, start a BFS and mark all reachable ‘O’s (e.g., as ‘1’).
  2. After BFS, flip all remaining ‘O’s to ‘X’ (these are surrounded), and all ‘1’s back to ‘O’.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
	void solve(vector<vector<char>>& board) {
		int m = board.size(), n = m ? board[0].size() : 0;
		if (!m || !n) return;
		auto bfs = [&](int x, int y) {
			queue<pair<int,int>> q; q.emplace(x, y);
			board[x][y] = '1';
			while (!q.empty()) {
				auto [i, j] = q.front(); q.pop();
				for (auto [di, dj] : vector<pair<int,int>>{{-1,0},{1,0},{0,-1},{0,1}}) {
					int ni = i+di, nj = j+dj;
					if (ni>=0 && ni<m && nj>=0 && nj<n && board[ni][nj]=='O') {
						board[ni][nj]='1'; q.emplace(ni, nj);
					}
				}
			}
		};
		for (int i = 0; i < m; ++i) {
			if (board[i][0] == 'O') bfs(i, 0);
			if (board[i][n-1] == 'O') bfs(i, n-1);
		}
		for (int j = 0; j < n; ++j) {
			if (board[0][j] == 'O') bfs(0, j);
			if (board[m-1][j] == 'O') bfs(m-1, j);
		}
		for (int i = 0; i < m; ++i)
			for (int j = 0; j < n; ++j)
				if (board[i][j] == 'O') board[i][j] = 'X';
				else if (board[i][j] == '1') board[i][j] = 'O';
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func solve(board [][]byte) {
	m, n := len(board), len(board[0])
	dirs := [][2]int{{-1,0},{1,0},{0,-1},{0,1}}
	bfs := func(x, y int) {
		q := [][2]int{{x, y}}
		board[x][y] = '1'
		for len(q) > 0 {
			i, j := q[0][0], q[0][1]; q = q[1:]
			for _, d := range dirs {
				ni, nj := i+d[0], j+d[1]
				if ni>=0 && ni<m && nj>=0 && nj<n && board[ni][nj]=='O' {
					board[ni][nj]='1'; q = append(q, [2]int{ni, nj})
				}
			}
		}
	}
	for i := 0; i < m; i++ {
		if board[i][0] == 'O' { bfs(i, 0) }
		if board[i][n-1] == 'O' { bfs(i, n-1) }
	}
	for j := 0; j < n; j++ {
		if board[0][j] == 'O' { bfs(0, j) }
		if board[m-1][j] == 'O' { bfs(m-1, j) }
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if board[i][j] == 'O' { board[i][j] = 'X' }
			if board[i][j] == '1' { board[i][j] = 'O' }
		}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

import java.util.*;
class Solution {
	public void solve(char[][] board) {
		if (board == null || board.length == 0 || board[0].length == 0) return;
		int m = board.length, n = board[0].length;
		for (int j = 0; j < n; j++) {
			if (board[0][j] == 'O') bfs(board, 0, j);
			if (board[m-1][j] == 'O') bfs(board, m-1, j);
		}
		for (int i = 0; i < m; i++) {
			if (board[i][0] == 'O') bfs(board, i, 0);
			if (board[i][n-1] == 'O') bfs(board, i, n-1);
		}
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 'O') board[i][j] = 'X';
				if (board[i][j] == '1') board[i][j] = 'O';
			}
	}
	private void bfs(char[][] board, int o, int p) {
		int m = board.length, n = board[0].length;
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[]{o, p});
		board[o][p] = '1';
		int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
		while (!queue.isEmpty()) {
			int[] top = queue.poll();
			int i = top[0], j = top[1];
			for (int[] d : dirs) {
				int ni = i + d[0], nj = j + d[1];
				if (ni >= 0 && ni < m && nj >= 0 && nj < n && board[ni][nj] == 'O') {
					board[ni][nj] = '1';
					queue.offer(new int[]{ni, nj});
				}
			}
		}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import java.util.*
class Solution {
	fun solve(board: Array<CharArray>) {
		val m = board.size; val n = board[0].size
		val dirs = arrayOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)
		fun bfs(x: Int, y: Int) {
			val q: Queue<Pair<Int,Int>> = LinkedList()
			q.add(x to y)
			board[x][y] = '1'
			while (q.isNotEmpty()) {
				val (i, j) = q.poll()
				for ((di, dj) in dirs) {
					val ni = i+di; val nj = j+dj
					if (ni in 0 until m && nj in 0 until n && board[ni][nj] == 'O') {
						board[ni][nj] = '1'; q.add(ni to nj)
					}
				}
			}
		}
		for (i in 0 until m) {
			if (board[i][0] == 'O') bfs(i, 0)
			if (board[i][n-1] == 'O') bfs(i, n-1)
		}
		for (j in 0 until n) {
			if (board[0][j] == 'O') bfs(0, j)
			if (board[m-1][j] == 'O') bfs(m-1, j)
		}
		for (i in 0 until m)
			for (j in 0 until n)
				when (board[i][j]) {
					'O' -> board[i][j] = 'X'
					'1' -> board[i][j] = 'O'
				}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

from collections import deque
class Solution:
	def solve(self, board: list[list[str]]) -> None:
		if not board: return
		m, n = len(board), len(board[0])
		def bfs(x, y):
			q = deque([(x, y)])
			board[x][y] = '1'
			while q:
				i, j = q.popleft()
				for di, dj in [(-1,0),(1,0),(0,-1),(0,1)]:
					ni, nj = i+di, j+dj
					if 0<=ni<m and 0<=nj<n and board[ni][nj]=='O':
						board[ni][nj]='1'; q.append((ni, nj))
		for i in range(m):
			if board[i][0] == 'O': bfs(i, 0)
			if board[i][n-1] == 'O': bfs(i, n-1)
		for j in range(n):
			if board[0][j] == 'O': bfs(0, j)
			if board[m-1][j] == 'O': bfs(m-1, j)
		for i in range(m):
			for j in range(n):
				if board[i][j] == 'O': board[i][j] = 'X'
				elif board[i][j] == '1': board[i][j] = 'O'
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

use std::collections::VecDeque;
impl Solution {
	pub fn solve(board: &mut Vec<Vec<char>>) {
		let m = board.len();
		let n = if m > 0 { board[0].len() } else { 0 };
		let dirs = [(-1,0),(1,0),(0,-1),(0,1)];
		let mut bfs = |x: usize, y: usize, board: &mut Vec<Vec<char>>| {
			let mut q = VecDeque::new();
			q.push_back((x, y));
			board[x][y] = '1';
			while let Some((i, j)) = q.pop_front() {
				for (di, dj) in dirs.iter() {
					let ni = i as isize + di;
					let nj = j as isize + dj;
					if ni>=0 && ni<m as isize && nj>=0 && nj<n as isize && board[ni as usize][nj as usize]=='O' {
						board[ni as usize][nj as usize]='1';
						q.push_back((ni as usize, nj as usize));
					}
				}
			}
		};
		for i in 0..m {
			if board[i][0] == 'O' { bfs(i, 0, board); }
			if board[i][n-1] == 'O' { bfs(i, n-1, board); }
		}
		for j in 0..n {
			if board[0][j] == 'O' { bfs(0, j, board); }
			if board[m-1][j] == 'O' { bfs(m-1, j, board); }
		}
		for i in 0..m {
			for j in 0..n {
				if board[i][j] == 'O' { board[i][j] = 'X'; }
				else if board[i][j] == '1' { board[i][j] = 'O'; }
			}
		}
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

function solve(board: string[][]): void {
	const m = board.length, n = board[0].length;
	function bfs(x: number, y: number) {
		const q: [number, number][] = [[x, y]];
		board[x][y] = '1';
		while (q.length) {
			const [i, j] = q.shift()!;
			for (const [di, dj] of [[-1,0],[1,0],[0,-1],[0,1]]) {
				const ni = i+di, nj = j+dj;
				if (ni>=0 && ni<m && nj>=0 && nj<n && board[ni][nj]==='O') {
					board[ni][nj]='1'; q.push([ni, nj]);
				}
			}
		}
	}
	for (let i = 0; i < m; i++) {
		if (board[i][0] === 'O') bfs(i, 0);
		if (board[i][n-1] === 'O') bfs(i, n-1);
	}
	for (let j = 0; j < n; j++) {
		if (board[0][j] === 'O') bfs(0, j);
		if (board[m-1][j] === 'O') bfs(m-1, j);
	}
	for (let i = 0; i < m; i++)
		for (let j = 0; j < n; j++)
			if (board[i][j] === 'O') board[i][j] = 'X';
			else if (board[i][j] === '1') board[i][j] = 'O';
}

Complexity

  • ⏰ Time complexity: O(mn) where m and n are the board’s dimensions (each cell is visited at most once).
  • 🧺 Space complexity: O(mn) in the worst case for the queue (all ‘O’s on the border).