Surrounded Regions
Problem Description
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 theboard.
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.
Example 1:
Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output:
Explanation:
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.lengthn == board[i].length1 <= m, n <= 200board[i][j]is'X'or'O'.
Solve it on LeetCode
Approaches
1. Simple DFS Approach
Intuition:
The problem can be approached using DFS to explore connected regions. The idea is to identify regions of 'O's connected to the boundary, which cannot be surrounded. All other 'O's can be flipped to 'X' as they are enclosed.
Steps:
- Traverse all boundary cells and run a DFS for each cell containing 'O'.
- In the DFS, mark every 'O' connected directly or indirectly as a safe entity (for example, temporarily replace 'O' with another character like '#').
- After marking, traverse the matrix again:
- Convert the safe '#'' back to 'O'.
- Change remaining 'O's to 'X'.
Code:
- Time Complexity: O(m * n), where m is the number of rows and n is the number of columns, as we might need to visit every cell.
- Space Complexity: O(m * n) due to the recursion stack.
2. Optimized BFS Approach
Intuition:
Instead of using DFS to solve the problem, we can use BFS. Using BFS helps to avoid the potential maximum recursion depth reached issue seen with DFS, especially with large matrices.
Steps:
- Use a queue data structure to implement BFS for boundary 'O's.
- Process in the same manner as DFS.
- At the end, convert '#' back to 'O' and rest 'O' to 'X'.
Code:
- Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
- Space Complexity: O(min(m, n)), which is the queue operational space for BFS.
3. Union-Find (Disjoint Set Union) Approach
Intuition:
Union-Find can be applied to efficiently manage connections. We can think of each cell as a node, and connect boundary 'O's to a dummy node as they can't be surrounded. All other unconnected 'O's are converted to 'X'.
Steps:
- Create a parent array for union-find.
- Connect every boundary 'O' to a dummy node.
- Connect internal 'O's with their neighbors if they are also 'O'.
- Finally, iterate over the board and change any 'O' not connected to the dummy node to 'X'.
Code:
- Time Complexity: O(m * n * α(m * n)), where α is the Inverse Ackermann function, which is practically constant.
- Space Complexity: O(m * n) for the parent array.