130. Surrounded Regions
Problem Description
In this problem, we are given a m x n matrix called board, composed of characters 'X' and 'O'. The goal is to identify all the regions formed by 'O' that are completely surrounded by 'X' in all four directions (up, down, left, and right) without any breaks. Once these regions are identified, we need to flip all the 'O's in those regions to 'X's. It's important to note that an 'O' on the boundary of the board isn't considered surrounded, and hence, the regions connected to an 'O' on the board boundary are safe and should not be flipped.
Intuition
The solution is based on the idea that an 'O' region would not be captured if it's connected directly or indirectly to an 'O' on the boundary of the board since it cannot be surrounded entirely by 'X's. To implement this, we apply depth-first search (DFS) to mark all 'O's that are connected to the boundary 'O's with a temporary marker (in this case, '.'). This multi-step approach ensures we only flip those 'O's into 'X's that are truly surrounded:
-
Identify Boundary-Connected 'O's: Iterate over the border rows and columns. For any 'O' found on the boundary, perform a DFS search to mark not only this 'O' but also any other 'O' connected to this one, directly or indirectly. We replace these 'O's temporarily with '.' to indicate they're safe from flipping.
-
Capture Surrounded Regions: After the DFS marking step, we go through the entire board to flip the remaining 'O's (those that are not marked with '.') into 'X's as they are surrounded by 'X's.
-
Restore Boundary-Connected Regions: Finally, we make another pass to convert all temporary markers '.' back into 'O's to restore the initial state for all the 'O's that were connected to the board boundary.
By taking this approach, we ensure to flip only those 'O's that are truly surrounded by 'X's, while preserving the boundary-connected 'O's.
Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.
Which algorithm should you use to find a node that is close to the root of the tree?
Solution Approach
The solution implements a depth-first search (DFS) algorithm to modify the matrix in place. Here's a walk-through of the code and the algorithms/data structures/patterns used in the solution:
-
Depth-First Search (DFS) Algorithm: The
dfsfunction is a classic implementation of the DFS algorithm. When it encounters an'O', it changes that'O'to a temporary marker'.'to indicate that it has been visited and should not be flipped later. Then, it checks adjacent cells (in all four directions) and recursively calls itself to mark connected 'O's.1def dfs(i, j): 2 board[i][j] = '.' 3 for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]: 4 x, y = i + a, j + b 5 if 0 <= x < m and 0 <= y < n and board[x][y] == 'O': 6 dfs(x, y) -
Boundary Cells Check: We iterate over the matrix looking for
'O's on the boundary edges. For every'O'found, thedfsfunction is called to start the marking process.1for i in range(m): 2 for j in range(n): 3 if board[i][j] == 'O' and ( 4 i == 0 or i == m - 1 or j == 0 or j == n - 1 5 ): 6 dfs(i, j) -
Flipping Surrounded 'O's Inside the Matrix: After marking all the boundary-connected
'O's with'.', we iterate over the matrix again. This time, we flip the unmarked'O's to'X's because they're surrounded by 'X's. The marked'.'cells retain information about boundary-connected 'O's and are not flipped.1for i in range(m): 2 for j in range(n): 3 if board[i][j] == 'O': 4 board[i][j] = 'X' -
Restoring the Boundary-Connected 'O's: In the last iteration over the matrix, we revert our temporary markers
'.'back to'O's, restoring their original state as they were not supposed to be flipped.1for i in range(m): 2 for j in range(n): 3 if board[i][j] == '.': 4 board[i][j] = 'O'
In this implementation, no additional data structures are needed as we modify the board in place. The pattern used here mainly revolves around the DFS algorithm, which is a powerful tool for searching or traversing through an adjacency graph, or in this case, a matrix, especially when we are dealing with connected components.
The solution has linear complexity with respect to the number of cells in the matrix since each cell is visited at most twice. Once during the DFS marking stage and once during the flipping stage. This ensures an efficient solution to the problem.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Example Walkthrough
Let's consider a small 3x4 board as an example:
1Board: 2O X X X 3X O O X 4X X X X
Step 1: Identify Boundary-Connected 'O's
We find that the 'O' in the top left corner is on the boundary. Applying the DFS algorithm starting from this 'O', we change it to a '.' to mark it as visited and safe:
1Board: 2. X X X 3X O O X 4X X X X
Since there are no other 'O's directly connected to the boundary 'O's, our board remains the same after the first step.
Step 2: Capture Surrounded Regions
Now, we scan through the rest of the board. The 'O's in the middle are surrounded by 'X's and there is no DFS path from any boundary 'O' to them. So we flip these 'O's to 'X's:
1Board: 2. X X X 3X X X X 4X X X X
Step 3: Restore Boundary-Connected Regions
Finally, we need to revert the '.' back to 'O', since it was marked only for the purpose of identification and not flipping:
1Board: 2O X X X 3X X X X 4X X X X
Our final board shows the 'O's in the middle flipped to 'X's, while the 'O' on the boundary remains intact. This concludes our walkthrough of how the depth-first search algorithm can be used to solve the problem of flipping all 'O's surrounded by 'X's on a board, while leaving the boundary-connected 'O's untouched.
Solution Implementation
1from typing import List # Importing the List type from typing module for type hinting
2
3class Solution:
4 def solve(self, board: List[List[str]]) -> None:
5 """
6 The function modifies the input 2D board (List of List of strings) in-place.
7 If an 'O' region is not surrounded by 'X' on the board's edges, it is flipped to 'X'.
8 'O' regions that are on the edges or connected to an edge 'O' region remain as 'O'.
9 """
10
11 def depth_first_search(i: int, j: int) -> None:
12 """Helper function to perform depth-first search and mark connected 'O's with a placeholder."""
13 board[i][j] = '.' # Temporary marking to keep track of visited and edge-connected 'O's
14 directions = [[0, -1], [0, 1], [1, 0], [-1, 0]] # Directions for exploring up, down, left, and right
15
16 # Explore adjacent cells in all 4 directions
17 for direction in directions:
18 x, y = i + direction[0], j + direction[1]
19 if 0 <= x < rows and 0 <= y < cols and board[x][y] == 'O':
20 depth_first_search(x, y)
21
22 # Board dimensions
23 rows, cols = len(board), len(board[0])
24
25 # First, traverse the border cells to find 'O's connected to borders
26 for i in range(rows):
27 for j in range(cols):
28 is_border_cell = i in (0, rows - 1) or j in (0, cols - 1)
29 if board[i][j] == 'O' and is_border_cell:
30 depth_first_search(i, j)
31
32 # Then, flip all the 'O' regions that are not on the border to 'X'
33 # and convert the previously marked border-connected 'O's back to 'O'
34 for i in range(rows):
35 for j in range(cols):
36 if board[i][j] == 'O':
37 board[i][j] = 'X'
38 elif board[i][j] == '.':
39 board[i][j] = 'O'
401class Solution {
2 private char[][] board; // Member variable to hold the input board
3 private int rows; // Number of rows in the board
4 private int cols; // Number of columns in the board
5
6 // Main function that solves the board by replacing all 'O' not surrounded by 'X' with 'X'
7 public void solve(char[][] board) {
8 rows = board.length; // Set the number of rows
9 cols = board[0].length; // Set the number of columns
10 this.board = board; // Initialize the board member variable
11
12 // Explore all 'O' on the borders, any 'O' connected to them should not be flipped
13 // hence temporarily mark them with '.'
14 for (int i = 0; i < rows; i++) {
15 for (int j = 0; j < cols; j++) {
16 // Condition to check if it's on the border and if it's an 'O'
17 if ((i == 0 || i == rows - 1 || j == 0 || j == cols - 1) && board[i][j] == 'O') {
18 depthFirstSearch(i, j); // Call DFS to mark the connected 'O's
19 }
20 }
21 }
22
23 // Flip all remaining 'O' to 'X' and back all '.' to 'O'.
24 for (int i = 0; i < rows; i++) {
25 for (int j = 0; j < cols; j++) {
26 // If it was marked '.', it's safe to flip it back to 'O'
27 if (board[i][j] == '.') {
28 board[i][j] = 'O';
29 }
30 // If it's still an 'O', it should be flipped to 'X' as it is not connected to a border
31 else if (board[i][j] == 'O') {
32 board[i][j] = 'X';
33 }
34 }
35 }
36 }
37
38 // Depth-first search function to find all the 'O's connected to a border 'O'
39 private void depthFirstSearch(int row, int col) {
40 board[row][col] = '.'; // Mark the cell as visited by replacing 'O' with '.'
41 int[] directions = {-1, 0, 1, 0, -1}; // Directions to move in the matrix
42 for (int k = 0; k < 4; k++) { // Loop through possible directions (up, right, down, left)
43 int nextRow = row + directions[k];
44 int nextCol = col + directions[k + 1];
45 // Check bounds and if the next cell is 'O', continue DFS
46 if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && board[nextRow][nextCol] == 'O') {
47 depthFirstSearch(nextRow, nextCol); // Recursive call for connected 'O's
48 }
49 }
50 }
51}
521class Solution {
2public:
3 // Main function to solve the board game
4 void solve(vector<vector<char>>& board) {
5 int rows = board.size(); // Number of rows in board
6 int cols = board[0].size(); // Number of columns in board
7
8 // Traverse the boundary of the board and perform DFS for 'O'
9 for (int i = 0; i < rows; ++i) {
10 for (int j = 0; j < cols; ++j) {
11 // Check if we're on the boundary of the board and the current cell is 'O'
12 bool isBoundary = i == 0 || i == rows - 1 || j == 0 || j == cols - 1;
13 if (isBoundary && board[i][j] == 'O') {
14 dfs(board, i, j); // Call DFS to mark connected 'O's
15 }
16 }
17 }
18
19 // Flip all remaining 'O's to 'X's, then flip marked '.' back to 'O'
20 for (int i = 0; i < rows; ++i) {
21 for (int j = 0; j < cols; ++j) {
22 if (board[i][j] == '.') {
23 board[i][j] = 'O'; // Restore temporarily marked 'O's
24 } else if (board[i][j] == 'O') {
25 board[i][j] = 'X'; // Flip untouched 'O's to 'X's
26 }
27 }
28 }
29 }
30
31 // Helper DFS function to mark connected 'O's starting from (i, j)
32 void dfs(vector<vector<char>>& board, int i, int j) {
33 board[i][j] = '.'; // Temporarily mark this 'O' to avoid repeated processing
34
35 // All possible directions to move (up, right, down, left)
36 vector<int> dirs = {-1, 0, 1, 0, -1};
37
38 // Traverse all directions
39 for (int k = 0; k < 4; ++k) {
40 int x = i + dirs[k]; // Next row index
41 int y = j + dirs[k + 1]; // Next column index
42
43 // Check if (x, y) is in bounds and is 'O'
44 bool inBounds = (x >= 0 && x < rows && y >= 0 && y < cols);
45 if (inBounds && board[x][y] == 'O') {
46 dfs(board, x, y); // Continue DFS for this 'O'
47 }
48 }
49 }
50};
511/**
2 * Solves the "Surrounded Regions" problem on a 2D board inplace by flipping surrounded 'O's to 'X's.
3 * Only 'O's on the border or connected to an 'O' on the border will remain as 'O'.
4 * @param board A 2D array of strings representing the board
5 */
6function solve(board: string[][]): void {
7 // Depth-first search to mark 'O's connected to the borders as temporary '.'
8 function depthFirstSearch(row: number, col: number) {
9 board[row][col] = '.';
10 const directions = [-1, 0, 1, 0, -1]; // Directions array to simplify the exploration of adjacent cells
11
12 // Explore all four directions
13 for (let k = 0; k < 4; ++k) {
14 const newRow = row + directions[k];
15 const newCol = col + directions[k + 1];
16
17 // If the new cell has 'O' and is within the bounds, continue the DFS
18 if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols && board[newRow][newCol] == 'O') {
19 depthFirstSearch(newRow, newCol);
20 }
21 }
22 }
23
24 const numRows = board.length;
25 const numCols = board[0].length;
26
27 // Start DFS from 'O's on the border
28 for (let row = 0; row < numRows; ++row) {
29 for (let col = 0; col < numCols; ++col) {
30 const isBorderCell = row == 0 || row == numRows - 1 || col == 0 || col == numCols - 1;
31 if (isBorderCell && board[row][col] == 'O') {
32 depthFirstSearch(row, col);
33 }
34 }
35 }
36
37 // Post-process to complete the flip of surrounded regions
38 for (let row = 0; row < numRows; ++row) {
39 for (let col = 0; col < numCols; ++col) {
40 if (board[row][col] == '.') {
41 board[row][col] = 'O'; // Restore temporary '.' to 'O'
42 } else if (board[row][col] == 'O') {
43 board[row][col] = 'X'; // Flip completely surrounded 'O's to 'X'
44 }
45 }
46 }
47}
48In a binary min heap, the minimum element can be found in:
Time and Space Complexity
Time Complexity
The time complexity of this algorithm is O(M*N), where M is the number of rows in the board and N is the number of columns. This is because the algorithm must visit every cell in the grid to perform the depth-first search (DFS) and the subsequent replacement of 'O's with 'X's.
DFS is invoked on cells that are on the border of the grid and are marked with 'O'. In the worst case, all border cells could be 'O's and the DFS would travel into every reachable 'O' from the border which can potentially cover the whole grid. Hence, the complexity considering the entire DFS calls collectively is linear with the number of cells, O(M*N).
After the DFS, the algorithm goes through all cells to replace remaining 'O's with 'X's and convert all temporary '.' markers back to 'O's. This is a straightforward double for-loop over the cells, which again results in a complexity of O(M*N).
Putting this together, despite having nested loops, the DFS does not visit cells more than once. Overall, the time complexity is O(M*N) as each cell is entered only once by the DFS.
Space Complexity
The space complexity of the algorithm is also O(M*N) in the worst-case scenario, due to the recursive nature of DFS. If the grid is filled with 'O's, the call stack for the DFS can grow as large as the number of cells in the grid before backtracking. This would be the case in a grid where one 'O' is connected to all other 'O's, thus the entire grid would be traversed without backtracking.
It is important to note that the space complexity assumes that the depth of the recursion stack is considered part of the space complexity. If the space used by the recursion stack is not considered, then the space complexity would be O(1) since the algorithm modifies the input grid in place and does not utilize additional space proportional to the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.