Devin's Blog

Surrounded Regions

3 min read

Intuition

  • The questions asks to convert O into X for any such O which falls into a region that does not “fall off” the map
  • i.e. if you ever have an O which leads to another O in that region which is on the outer perimeter, then this O is not captured.
  • So, to solve the question, start by finding all such O’s that cannot be captured (by running DFS starting from all outer perimeter O’s) then convert anything that is not in that resulting set to an X.
  • This question is reducibkle

Complexity

Runtime

since we have to go through the entire M by N grid in all cases.

Space

in the case where the entire grid is filled with O’s, since that many DFS recursive calls occur.

Code

Multi Source BFS

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        m, n = len(board), len(board[0])
        q = deque()
 
        # Multi source BFS from O's in perimeter
        for r in range(m):
            if board[r][0] == 'O':
                q.append((r, 0))
            if board[r][n - 1] == 'O':
                q.append((r, n - 1))
        
        for c in range(n):
            if board[0][c] == 'O':
                q.append((0, c))
            if board[m - 1][c] == 'O':
                q.append((m - 1, c))
        
        def is_inbounds(r, c):
            return 0 <= r < m and 0 <= c < n
 
        def adj(r, c):
            return [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)] # left, right, up, down
 
        visited = set(q)
        res = q.copy()
        while q:
            r, c = q.popleft()
            for x, y in adj(r, c):
                if is_inbounds(x, y) and (x, y) not in visited:
                    visited.add((x, y))
                    if board[x][y] == 'O':
                        res.append((x, y))
                        q.append((x, y))
        
        for r in range(m):
            for c in range(n):
                if board[r][c] == 'O' and (r, c) not in res:
                    board[r][c] = 'X'

DFS

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        m, n = len(board), len(board[0])
 
        def adj(r, c):
            return [(i, j) for i, j in \
             [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)] if \
             0 <= i < m and 0 <= j < n]
 
        visited = set()
        def dfs(r, c):
            visited.add((r, c))
            for i, j in adj(r, c):
                if board[i][j] == 'O' and (i, j) not in visited:
                    dfs(i, j)
 
        for c in range(n):
            if board[0][c] == 'O':
                dfs(0, c)
            if board[m - 1][c] == 'O':
                dfs(m - 1, c)
        
        for r in range(m):
            if board[r][0] == 'O':
                dfs(r, 0)
            if board[r][n - 1] == 'O':
                dfs(r, n - 1)
 
        for r in range(m):
            for c in range(n):
                if board[r][c] == 'O' and (r, c) not in visited:
                    board[r][c] = 'X'

Notes

Drive

Cards

START Basic Front: Surrounded Regions Back: Run BFS on outer perimeter O’s, and convert to X all O’s not touched by the DFS runthrough. END

References

Graph View