In this guide, you will get 130. Surrounded Regions LeetCode Solution with the best time and space complexity. The solution to Surrounded Regions problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You are given an m x n matrix board containing letters ‘X’ and ‘O’, capture regions that are surrounded:
Connect: A cell is connected to adjacent cells horizontally or vertically.
Region: To form a region connect every ‘O’ cell.
Surround: The region is surrounded with ‘X’ cells if you can connect the region with ‘X’ cells and none of the region cells are on the edge of the board.
To capture a surrounded region, replace all ‘O’s with ‘X’s in-place within the original board. You do not need to return anything.
In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.
Example 2:
Input: board = [[“X”]]
Output: [[“X”]]
Constraints:
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is 'X' or 'O'.
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(1)
130. Surrounded Regions LeetCode Solution in C++
class Solution {
public:
void solve(vector<vector<char>>& board) {
if (board.empty())
return;
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int m = board.size();
const int n = board[0].size();
queue<pair<int, int>> q;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i * j == 0 || i == m - 1 || j == n - 1)
if (board[i][j] == 'O') {
q.emplace(i, j);
board[i][j] = '*';
}
// Mark the grids that stretch from the four sides with '*'.
while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (board[x][y] != 'O')
continue;
q.emplace(x, y);
board[x][y] = '*';
}
}
for (vector<char>& row : board)
for (char& c : row)
if (c == '*')
c = 'O';
else if (c == 'O')
c = 'X';
}
}; /* code provided by PROGIEZ */
130. Surrounded Regions LeetCode Solution in Java
class Solution {
public void solve(char[][] board) {
if (board.length == 0)
return;
final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
final int m = board.length;
final int n = board[0].length;
Queue<Pair<Integer, Integer>> q = new ArrayDeque<>();
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (i * j == 0 || i == m - 1 || j == n - 1)
if (board[i][j] == 'O') {
q.offer(new Pair<>(i, j));
board[i][j] = '*';
}
// Mark the grids that stretch from the four sides with '*'.
while (!q.isEmpty()) {
final int i = q.peek().getKey();
final int j = q.poll().getValue();
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (board[x][y] != 'O')
continue;
q.offer(new Pair<>(x, y));
board[x][y] = '*';
}
}
for (char[] row : board)
for (int i = 0; i < row.length; ++i)
if (row[i] == '*')
row[i] = 'O';
else if (row[i] == 'O')
row[i] = 'X';
}
} // code provided by PROGIEZ
130. Surrounded Regions LeetCode Solution in Python
class Solution:
def solve(self, board: list[list[str]]) -> None:
if not board:
return
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
m = len(board)
n = len(board[0])
q = collections.deque()
for i in range(m):
for j in range(n):
if i * j == 0 or i == m - 1 or j == n - 1:
if board[i][j] == 'O':
q.append((i, j))
board[i][j] = '*'
# Mark the grids that stretch from the four sides with '*'.
while q:
i, j = q.popleft()
for dx, dy in dirs:
x = i + dx
y = j + dy
if x < 0 or x == m or y < 0 or y == n:
continue
if board[x][y] != 'O':
continue
q.append((x, y))
board[x][y] = '*'
for row in board:
for i, c in enumerate(row):
row[i] = 'O' if c == '*' else 'X' # code by PROGIEZ
