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

1.0. Intuition

1. How do we traverse the grid? We have to use BFS/DFS.
2. How do we distinguish between the ‘O’ connected on the boundary to the ‘O’s present inside?
3. 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

1.1. Logic

• 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

2.0. Code

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[0])
        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.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.