Surrounded Regions

Patrick Leaton
Published: Nov. 7, 2021, 7:27 p.m.
Problem Description

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

 

Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

Example 2:

Input: board = [["X"]]
Output: [["X"]]

 

Constraints:

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] is 'X' or 'O'.

 

The description was taken from https://leetcode.com/problems/surrounded-regions/.

Problem Solution

#O(M*N) Time, O(M*N) Space
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        edge_regions = {}
        m, n = len(board), len(board[0])
       
        def in_bounds(row:int, col:int) -> bool:
            if row < 0 or col < 0 or row >= m or col >= n:
                return False
            if board[row][col] != "O":
                return False
            if (row, col) in edge_regions:
                return False
            return True
       
        def dfs(row:int, col:int, edge:bool) -> None:
            if not in_bounds(row, col):
                return
            if edge:
                edge_regions[(row, col)] = True
            else:
                board[row][col] = "X"
            dfs(row+1, col, edge)
            dfs(row-1, col, edge)
            dfs(row, col+1, edge)
            dfs(row, col-1, edge)
       
        for row in range(m):
            dfs(row, 0, True)
            dfs(row, n-1, True)
       
        for col in range(n):
            dfs(0, col, True)
            dfs(m-1, col, True)
       
        for row in range(1, m-1):
            for col in range(1, n-1):
                if board[row][col] == "O":
                    dfs(row, col, False)

Problem Explanation

If we are given a grid of islands, that is usually an indication that a Depth-First Search will be required.

A Depth-First Search is typically more favorable for navigating these weird nonlinear paths where a BFS is more favorable for finding the shortest paths or whether a path exists.

In this problem, we are only going to want to sink the islands that are surrounded, meaning they aren't on the edge.

To handle this, we can perform an initial DFS on the borders of the grid first and place the coordinates of each region cell on the edge into a HashMap.  This way, if we encounter the region later, we will know it is on the edge so we should disregard it.

After doing that, we can then perform a second DFS and sink any region cell that isn't in the edge region HashMap.

Let's start by initializing our edge regions dictionary and saving the length and width of the grid so that we don't have to keep rewriting these later.

        edge_regions = {}
        m, n = len(board), len(board[0])

Next, we will create a helper function to let us know whether we should visit a given cell.

If the cell is outside the bounds of the grid, is not part of an open region, or has already been visited on an edge, we will return false.

Otherwise, we will return true that we should visit it.

        def in_bounds(row:int, col:int) -> bool:
            if row < 0 or col < 0 or row >= m or col >= n:
                return False
            if board[row][col] != "O":
                return False
            if (row, col) in edge_regions:
                return False
            return True

Next, we will make our DFS function.

This function will take a row, column, and edge flag which will signify that we arrived at the current cell from an edge.

        def dfs(row:int, col:int, edge:bool) -> None:

 

If the current cell is not in bounds according to our previous helper function, we will return from it.

            if not in_bounds(row, col):
                return

 

If we arrived at the current cell from an edge, we will add the coordinates to the edge regions dictionary.

            if edge:
                edge_regions[(row, col)] = True

 

Otherwise, we will flip it to be captured.

            else:
                board[row][col] = "X"

 

After, we will continue the DFS on the four surrounding neighbors.

            dfs(row+1, col, edge)
            dfs(row-1, col, edge)
            dfs(row, col+1, edge)
            dfs(row, col-1, edge)

Now that we have our helper functions built, we will begin our edge DFS traversals.

We will first run the DFS to mark any edge regions on the left and right columns.

        for row in range(m):
            dfs(row, 0, True)
            dfs(row, n-1, True)

 

Then, we will run the DFS to mark any edge regions on the top and bottom rows.

        for col in range(n):
            dfs(0, col, True)
            dfs(m-1, col, True)

 

Lastly, we will traverse the grid once more, excluding the edge rows and columns.

If we encounter a region cell, we will run the DFS on it to capture the region.

        for row in range(1, m-1):
            for col in range(1, n-1):
                if board[row][col] == "O":
                    dfs(row, col, False)