Depth-First Search
Surrounded Regions
DESCRIPTION (inspired by Leetcode.com)
Given an m x n matrix grid containing only characters 'X' and 'O', modify grid to replace all regions of 'O' that are completey surrounded by 'X' with 'X'.
A region of 'O' is surrounded by 'X' if there is no adjacent path (cells that border each other in the N, W, E, S directions) consisting of only 'O' from anywhere inside that region to the border of the board.
Input:
grid = [ ["X","X","X","X","O"], ["X","X","O","X","X"], ["X","X","O","X","O"], ["X","O","X","X","X"] ["X","O","X","X","X"] ]
Output:
[ ["X","X","X","X","O"], ["X","X","X","X","X"], ["X","X","X","X","O"], ["X","O","X","X","X"], ["X","O","X","X","X"] ]
Explanation: The region of O's at grid[1][2] and grid[2][2] is completely surrounded, so we replace them with X's. All the other "O"s are connected to the border by a path of all "O"s, so we leave them as is.
Input:
grid = [ ["O","O"], ["O","X"], ]
Output:
[ ["O", "O"], ["O", "X"] ]
Explanation: All the "O"s are connected to the border.
Explanation
class Solution:def surrounded_regions(self, grid):if not grid:return gridrows = len(grid)cols = len(grid[0])# recursive function to find all the "O"s that are reachable# from the border and mark them as "S"def dfs(x, y):# return immediately if the cell is out of bounds or is not an "Oif x < 0 or y < 0 or x >= rows or y >= cols or grid[x][y] != 'O':returngrid[x][y] = 'S'# explore the neighboring cellsdfs(x + 1, y)dfs(x - 1, y)dfs(x, y + 1)dfs(x, y - 1)# initialize the dfs for the first and last columnfor i in range(rows):if grid[i][0] == 'O':dfs(i, 0)if grid[i][cols - 1] == 'O':dfs(i, cols - 1)# initialize the dfs for the first and last rowfor j in range(cols):if grid[0][j] == 'O':dfs(0, j)if grid[rows - 1][j] == 'O':dfs(rows - 1, j)# change the "O"s that are not marked as "S" to "X"s and the "S"s back to "O"sfor i in range(rows):for j in range(cols):if grid[i][j] == 'O':grid[i][j] = 'X'elif grid[i][j] == 'S':grid[i][j] = 'O'return grid
Keeping Track of Visited Cells
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(M * N) where M is the number of rows and N is the number of columns in the grid. We perform a DFS traversal (visiting each cell at most once) and then iterate through the entire grid to update the cell values.
Space Complexity: O(M * N) where M is the number of rows and N is the number of columns in the grid. We have to allocate space for each recursive call in the call stack, which can be at most O(M * N).
Your account is free and you can post anonymously if you choose.