grid47 Exploring patterns and algorithms
Oct 25, 2024
7 min read
Solution to LeetCode 130: Surrounded Regions Problem
You are given an m x n matrix board containing letters ‘X’ and ‘O’. Capture all regions that are surrounded by ‘X’. A region is captured if it is surrounded by ‘X’ cells and cannot reach the edges of the board.
Problem
Approach
Steps
Complexity
Input: The input is an m x n matrix containing 'X' and 'O'. Each element represents a cell of the board.
• Explanation: In this case, 'O's that are surrounded by 'X's (not touching the edge) are captured and turned into 'X's.
• Input: [['X']]
• Explanation: This board has no 'O's, so no cells are captured and the board remains unchanged.
Approach: Use depth-first search (DFS) to mark all 'O' cells connected to the borders, then modify the matrix accordingly.
Observations:
• The 'O' cells on the borders and connected to them are safe, and need to be preserved.
• The remaining 'O' cells are surrounded and need to be captured.
• The problem can be solved efficiently by marking the border-connected 'O' cells as safe using DFS, and then replacing all remaining 'O's with 'X'.
Steps:
• 1. Iterate through the board and perform DFS from any 'O' cells found on the borders.
• 2. Mark the connected 'O' cells as safe by changing them to a temporary value, like '1'.
• 3. After completing the DFS, iterate through the board again to replace all 'O' cells with 'X'.
• 4. Restore the safe 'O' cells (those marked '1') back to 'O'.
Empty Inputs:
• If the board is empty or contains only 'X', no changes are made.
Large Inputs:
• The algorithm should be efficient enough to handle the maximum constraints of m, n <= 200.
Special Values:
• If the board contains no 'O' cells, no modifications will occur.
Constraints:
• The board will contain at least one row and one column.
voidsolve(vector<vector<char>>& board) {
int m = board.size(), n = board[0].size();
for(int i =0; i < m; i++)
for(int j =0; j < n; j++)
if(i ==0|| j ==0|| i == m -1|| j == n -1)
if(board[i][j] =='O')
dfs(board, i, j);
for(int i =0; i < m; i++)
for(int j =0; j < n; j++)
if(board[i][j] =='O')
board[i][j] ='X';
elseif(board[i][j] =='1')
board[i][j] ='O';
}
voiddfs(vector<vector<char>>&grid, int i, int j) {
if(i <0|| j <0|| i == grid.size() || j == grid[0].size() || grid[i][j] !='O')
return;
grid[i][j] ='1';
dfs(grid, i +1, j);
dfs(grid, i, j +1);
dfs(grid, i -1, j);
dfs(grid, i, j -1);
}
1 : Function Declaration
voidsolve(vector<vector<char>>& board) {
Define the function `solve` that takes a 2D grid `board` as input and modifies it in-place to solve the problem.
2 : Matrix Dimensions
int m = board.size(), n = board[0].size();
Get the dimensions of the grid: `m` represents the number of rows and `n` represents the number of columns.
3 : Outer Loop Iteration
for(int i =0; i < m; i++)
Start an outer loop to iterate over each row of the board.
4 : Inner Loop Iteration
for(int j =0; j < n; j++)
Start an inner loop to iterate over each column of the current row.
5 : Boundary Check
if(i ==0|| j ==0|| i == m -1|| j == n -1)
Check if the current position is at the border of the grid (first or last row/column).
6 : O Check
if(board[i][j] =='O')
Check if the current cell is 'O', indicating a potential region to explore.
7 : DFS Call
dfs(board, i, j);
Call the `dfs` function to perform Depth-First Search and mark all connected 'O's starting from the current cell.
8 : Second Outer Loop Iteration
for(int i =0; i < m; i++)
Start the second iteration over the rows of the grid to modify the cells based on DFS results.
9 : Second Inner Loop Iteration
for(int j =0; j < n; j++)
Iterate over the columns of each row in the second pass.
10 : O Replacement
if(board[i][j] =='O')
Check if the current cell is 'O' that was not connected to the border (should be surrounded by 'X').
11 : Mark X
board[i][j] ='X';
Change the isolated 'O' to 'X' since it is surrounded by 'X'.
12 : Restore O
elseif(board[i][j] =='1')
Check if the current cell was marked as '1' during the DFS, indicating it is part of a border-connected region.
13 : Restore O
board[i][j] ='O';
Restore the 'O' at this position since it was connected to the border.
14 : DFS Function Declaration
voiddfs(vector<vector<char>>&grid, int i, int j) {
Define the `dfs` function that performs Depth-First Search to explore connected regions of 'O'.
15 : Base Case Check
if(i <0|| j <0|| i == grid.size() ||
Check if the current position is out of bounds of the grid.
16 : DFS Exit Condition
j == grid[0].size() || grid[i][j] !='O')
Check if the current cell is not 'O' (i.e., already visited or not a valid cell for DFS).
17 : Return Statement
return;
Exit the DFS function if the base case is met.
18 : Mark as Visited
grid[i][j] ='1';
Mark the current cell as visited by changing it to '1'.
19 : Recursive DFS Calls
dfs(grid, i +1, j);
Recursively call `dfs` to explore the cell below the current one.
20 : Recursive DFS Calls
dfs(grid, i, j +1);
Recursively call `dfs` to explore the cell to the right of the current one.
21 : Recursive DFS Calls
dfs(grid, i -1, j);
Recursively call `dfs` to explore the cell above the current one.
22 : Recursive DFS Calls
dfs(grid, i, j -1);
Recursively call `dfs` to explore the cell to the left of the current one.
Best Case: O(m * n), where m is the number of rows and n is the number of columns.
Average Case: O(m * n), since we traverse all cells at least once.
Worst Case: O(m * n), since we may need to explore all cells in the matrix.
Description: The time complexity is linear with respect to the size of the board.
Best Case: O(1), if no extra space is used (except for temporary marking).
Worst Case: O(m * n), since we might use extra space for the DFS stack in the worst case.
Description: The space complexity is dependent on the recursion depth of DFS, but in practice it is O(m * n).
