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:

a grid of X and Os for the problem Surrounded Regions
a grid of X and Os for the problem Surrounded Regions

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.

transformation example for Surrounded Regions problem
transformation example for Surrounded Regions problem

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.

    Leave a Reply

    Your email address will not be published. Required fields are marked *