Surrounded Regions
Surrounded Regions – Medium Level Problem
You are given a 2D grid (matrix) with the characters ‘X’ and ‘O’.
If a group of ‘O’s is completely enclosed by ‘X’s on all four sides (up, down, left, and right), it is considered surrounded.
Your task is to replace all such surrounded ‘O’s with ‘X’s directly in the given grid. Make the changes without using extra space for another grid.
Example 1:
Input: board = [
["X","X","X","X"],
["X","O","O","X"],
["X","O","O","X"],
["X","X","X","O"]
]
Output: [
["X","X","X","X"],
["X","X","X","X"],
["X","X","X","X"],
["X","X","X","O"]
]
["X","X","X","X"],
["X","O","O","X"],
["X","O","O","X"],
["X","X","X","O"]
]
Output: [
["X","X","X","X"],
["X","X","X","X"],
["X","X","X","X"],
["X","X","X","O"]
]
Explanation: Note that regions that are on the border are not considered surrounded regions.
Constraints :
- 1 <= board.length, board[i].length <= 200
- board[i][j] is ‘X’ or ‘O’.
Surrounded Regions Problem - Solution
Recommendation for Time and Space Complexity – Aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the grid.
Hints for solving problems
Hint 1
Focus on regions of ‘O’ that are not connected to the border. These are the ones surrounded by ‘X’. Think about how to identify which ‘O’s are connected to the border.
Hint 2
Use Depth First Search (DFS). Instead of finding surrounded regions directly, mark the regions connected to border ‘O’s to separate them.
Hint 3
Run DFS from every border ‘O’, marking connected cells with ‘#’. After that, traverse the grid:
- Convert remaining ‘O’s to ‘X’ (surrounded regions).
- Convert ‘#’ back to ‘O’ (border-connected regions).
There are mainly 3 approach to solve this problem-
- Depth First Search Method
- Breadth First Search Method
1. Depth First Search Method
Use DFS to explore all ‘O’s connected to the border and mark them temporarily (e.g., as ‘#’). After the DFS traversal, convert the remaining ‘O’s (surrounded) to ‘X’, and revert ‘#’ back to ‘O’.
- Time complexity: O(m * n)
- Space complexity: O(m * n)
where m is the number of rows and n is the number of columns of the board.
Code
C++
Java
Python
JavaScript
C++
class Solution {
int ROWS, COLS;
public:
void solve(vector<vector<char>>& board) {
ROWS = board.size();
COLS = board[0].size();
for (int r = 0; r < ROWS; r++) {
if (board[r][0] == 'O') {
capture(board, r, 0);
}
if (board[r][COLS - 1] == 'O') {
capture(board, r, COLS - 1);
}
}
for (int c = 0; c < COLS; c++) {
if (board[0][c] == 'O') {
capture(board, 0, c);
}
if (board[ROWS - 1][c] == 'O') {
capture(board, ROWS - 1, c);
}
}
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] == 'O') {
board[r][c] = 'X';
} else if (board[r][c] == 'T') {
board[r][c] = 'O';
}
}
}
}
private:
void capture(vector<vector<char>>& board, int r, int c) {
if (r < 0 || c < 0 || r >= ROWS ||
c >= COLS || board[r][c] != 'O') {
return;
}
board[r][c] = 'T';
capture(board, r + 1, c);
capture(board, r - 1, c);
capture(board, r, c + 1);
capture(board, r, c - 1);
}
};
Java
public class Solution {
private int ROWS, COLS;
public void solve(char[][] board) {
ROWS = board.length;
COLS = board[0].length;
for (int r = 0; r < ROWS; r++) {
if (board[r][0] == 'O') {
capture(board, r, 0);
}
if (board[r][COLS - 1] == 'O') {
capture(board, r, COLS - 1);
}
}
for (int c = 0; c < COLS; c++) {
if (board[0][c] == 'O') {
capture(board, 0, c);
}
if (board[ROWS - 1][c] == 'O') {
capture(board, ROWS - 1, c);
}
}
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] == 'O') {
board[r][c] = 'X';
} else if (board[r][c] == 'T') {
board[r][c] = 'O';
}
}
}
}
private void capture(char[][] board, int r, int c) {
if (r < 0 || c < 0 || r >= ROWS ||
c >= COLS || board[r][c] != 'O') {
return;
}
board[r][c] = 'T';
capture(board, r + 1, c);
capture(board, r - 1, c);
capture(board, r, c + 1);
capture(board, r, c - 1);
}
}
Python
class Solution:
def solve(self, board: List[List[str]]) -> None:
ROWS, COLS = len(board), len(board[0])
def capture(r, c):
if (r < 0 or c < 0 or r == ROWS or
c == COLS or board[r][c] != "O"
):
return
board[r][c] = "T"
capture(r + 1, c)
capture(r - 1, c)
capture(r, c + 1)
capture(r, c - 1)
for r in range(ROWS):
if board[r][0] == "O":
capture(r, 0)
if board[r][COLS - 1] == "O":
capture(r, COLS - 1)
for c in range(COLS):
if board[0][c] == "O":
capture(0, c)
if board[ROWS - 1][c] == "O":
capture(ROWS - 1, c)
for r in range(ROWS):
for c in range(COLS):
if board[r][c] == "O":
board[r][c] = "X"
elif board[r][c] == "T":
board[r][c] = "O"
JavaScript
class Solution {
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
solve(board) {
let ROWS = board.length, COLS = board[0].length;
const capture = (r, c) => {
if (r < 0 || c < 0 || r == ROWS ||
c == COLS || board[r][c] !== 'O') {
return;
}
board[r][c] = 'T';
capture(r + 1, c);
capture(r - 1, c);
capture(r, c + 1);
capture(r, c - 1);
}
for (let r = 0; r < ROWS; r++) {
if (board[r][0] === 'O') capture(r, 0);
if (board[r][COLS - 1] === 'O') capture(r, COLS - 1);
}
for (let c = 0; c < COLS; c++) {
if (board[0][c] === 'O') capture(0, c);
if (board[ROWS - 1][c] === 'O') capture(ROWS - 1, c);
}
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
if (board[r][c] === 'O') board[r][c] = 'X';
else if (board[r][c] === 'T') board[r][c] = 'O';
}
}
}
}
2. Breadth First Search Method
Similar to DFS, use BFS starting from all border ‘O’s to mark the connected regions with a temporary marker (e.g., ‘#’). Finally, update the grid by flipping the remaining ‘O’s to ‘X’ and reverting ‘#’ to ‘O’.
- Time complexity: O(m * n)
- Space complexity: O(m * n)
where m is the number of rows and n is the number of columns of the board.
Code
C++
Java
Python
JavaScript
C++
class Solution {
int ROWS, COLS;
vector<pair<int, int>> directions = {{1, 0}, {-1, 0},
{0, 1}, {0, -1}};
public:
void solve(vector<vector<char>>& board) {
ROWS = board.size();
COLS = board[0].size();
capture(board);
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] == 'O') {
board[r][c] = 'X';
} else if (board[r][c] == 'T') {
board[r][c] = 'O';
}
}
}
}
private:
void capture(vector<vector<char>>& board) {
queue<pair<int, int>> q;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) { if (r == 0 || r == ROWS - 1 || c == 0 || c == COLS - 1 && board[r][c] == 'O') { q.push({r, c}); } } } while (!q.empty()) { auto [r, c] = q.front(); q.pop(); if (board[r][c] == 'O') { board[r][c] = 'T'; for (auto& direction : directions) { int nr = r + direction.first; int nc = c + direction.second; if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS) {
q.push({nr, nc});
}
}
}
}
}
};
Java
public class Solution {
private int ROWS, COLS;
private int[][] directions = new int[][]{
{1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
public void solve(char[][] board) {
ROWS = board.length;
COLS = board[0].length;
capture(board);
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (board[r][c] == 'O') {
board[r][c] = 'X';
} else if (board[r][c] == 'T') {
board[r][c] = 'O';
}
}
}
}
private void capture(char[][] board) {
Queue<int[]> q = new LinkedList<>();
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) { if (r == 0 || r == ROWS - 1 || c == 0 || c == COLS - 1 && board[r][c] == 'O') { q.offer(new int[]{r, c}); } } } while (!q.isEmpty()) { int[] cell = q.poll(); int r = cell[0], c = cell[1]; if (board[r][c] == 'O') { board[r][c] = 'T'; for (int[] direction : directions) { int nr = r + direction[0], nc = c + direction[1]; if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS) {
q.offer(new int[]{nr, nc});
}
}
}
}
}
}
Python
class Solution:
def solve(self, board: List[List[str]]) -> None:
ROWS, COLS = len(board), len(board[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def capture():
q = deque()
for r in range(ROWS):
for c in range(COLS):
if (r == 0 or r == ROWS - 1 or
c == 0 or c == COLS - 1 and
board[r][c] == "O"
):
q.append((r, c))
while q:
r, c = q.popleft()
if board[r][c] == "O":
board[r][c] = "T"
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < ROWS and 0 <= nc < COLS:
q.append((nr, nc))
capture()
for r in range(ROWS):
for c in range(COLS):
if board[r][c] == "O":
board[r][c] = "X"
elif board[r][c] == "T":
board[r][c] = "O"
JavaScript
class Solution {
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
solve(board) {
let ROWS = board.length, COLS = board[0].length;
let directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const capture = () => {
let q = [];
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) { if (r === 0 || r === ROWS - 1 || c === 0 || c === COLS - 1 && board[r][c] === 'O') { q.push([r, c]); } } } while (q.length) { let [r, c] = q.shift(); if (board[r][c] === 'O') { board[r][c] = 'T'; for (let [dr, dc] of directions) { let nr = r + dr, nc = c + dc; if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS) {
q.push([nr, nc]);
}
}
}
}
}
capture();
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
if (board[r][c] === 'O') board[r][c] = 'X';
else if (board[r][c] === 'T') board[r][c] = 'O';
}
}
}
}
