Surrounded Regions | DFS Solution Explained
LeetCode 130. Surrounded Regions. I solve the problem using DFS approach. This is more of an implementation based question. Problem Link.
0. Surrounded Regions: Problem Discussion
Given a grid of ‘X’ and ‘O’s like such:
We focus on ‘O’s. If an O is present on the boundary – or is connected by a chain of ‘O’s to an ‘O’ on the boundary, we keep it as is. However, all the remaining ‘O’s get converted to ‘X’s.
1. Surrounded Regions: Observations
- How do we traverse the grid? We have to use BFS/DFS.
- How do we distinguish between the ‘O’ connected on the boundary to the ‘O’s present inside?
- How do we keep a track of visited cells?
Core observation: We can answer the questions 2 and 3 together by creating an intermediate state.
- One way is to run a DFS from all the boundary connected ‘O’s and convert them all to an intermediate state, say ‘#’.
- Then, once we are done with the search, we are left with a gird that has the following properties:
- X remain intact
- Os connected on the outside get converted to #s
- Os not connected thus become Xs
- Initialize a DFS from all the Os on the boundary. For each DFS:
- Continue exploring in all the directions, till you see Os
- Convert all the Os in this case to #s
- Once done, we convert:
- all the remaining Os to Xs
- all the #s to Os
2. Surrounded Regions: Code & Complexity Analysis
class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ def dfs(x, y): if not (0 <= x < m and 0 <= y < n): return if board[x][y] == 'O': board[x][y] = '#' for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]: nx, ny = x+dx, y+dy dfs(nx, ny) m, n = len(board), len(board) for x in range(m): dfs(x, 0) dfs(x, n-1) for y in range(n): dfs(0, y) dfs(m-1, y) for x in range(m): for y in range(n): if board[x][y] == 'O': board[x][y] = 'X' for x in range(m): for y in range(n): if board[x][y] == '#': board[x][y] = 'O' return
2.1. Complexity Analysis
- Time: O(MN). Worst case, the grid is full of Os and we end up going over all them once.
- Space: O(MN). While we modify the board in-place, the height of the recursion call stack can be O(MN), for the case described above.
June 13, 2022