Start learning free

LESSON 505 OF 573 · GRAPHS

Surrounded Regions in Go: BFS from the Border

Practice O(m · n) Read the full explanation

You are given board, a grid of m rows and n columns in which every cell holds the letter 'X' or the letter 'O'. It is an array of rows, and each row is an array of single letters.

Two 'O' cells are connected when one is directly above, below, left or right of the other (not diagonally). A region is a group of 'O' cells that can all be reached from each other through connected cells, and that no other 'O' is connected to.

A region is surrounded when none of its cells lies on the edge of the board (the first or the last row, the first or the last column): 'X' cells close it in on every side. Capture every surrounded region by changing all of its cells to 'X'. A region with at least one cell on the edge is not captured and stays as it is.

Change board in place and return nothing: the board you were given must hold the result.

 

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: The three red cells form one region, and none of them is on the edge, so it is
captured. The green 'O' is in the last row, on the edge: it is not captured.

Example 2:

Input: board =
O

Output:
O

Explanation: The only cell is on every edge of the board, so it is not captured.

Example 3:

Input: board =
O X X X X
X O O O X
X X X O X
X O X O X
X X X O X

Output:
O X X X X
X O O O X
X X X O X
X X X O X
X X X O X

Explanation: The green region in the middle winds down to the 'O' in the last row, which is on
the edge, so none of it is captured. The 'O' in the top-left corner touches that region only diagonally,
which doesn't connect them, but it is on the edge itself. The red 'O' is closed in by 'X' on all four
sides: it is captured.

 

Constraints:

  • 1 <= m, n <= 200
  • Every row has n cells.
  • Every cell is 'X' or 'O'.

Note:

Your algorithm should run in O(m · n) time and use O(m · n) extra space.

Checking every 'O' on its own, with a search that looks for a way to the edge, can cost O((m · n)2): think of one large region in the middle of the board that is searched again from each of its cells. The tutorial turns the question around, as Pacific Atlantic Water Flow does, and starts from the edge. Every 'O' on the edge is safe, and so is every 'O' connected to a safe one. A BFS that starts from all the 'O's on the edge at once marks every safe cell, and each cell joins its queue at most once. Then one pass over the board turns every 'O' that is not marked into 'X'.

Use a queue, or a stack of your own, rather than recursion: one region can wind through the whole board, and a recursive search tens of thousands of calls deep runs out of call stack in some languages.

STEP 1 OF 23
    Ctrl + Enter to check

    GO · GRAPHS

    Surrounded Regions in Go, explained

    Problem overview

    The function solve receives board, a [][]byte grid in which every cell is 'X' or 'O'. Two 'O' cells are connected when one is directly above, below, left or right of the other; diagonal neighbours don't count. A region is a group of connected 'O' cells. A region is surrounded when none of its cells lies on the edge of the board, that is, in the first or last row or the first or last column. The function must change every surrounded region to 'X', in place, and return nothing. A region with a cell on the edge stays as it is.

    In the first example, the board is

    X X X X
X O O X
X X O X
X O X X

    The three 'O' cells in the middle form one region, and none is on the edge, so they are captured. The 'O' in the last row is on the edge and stays:

    X X X X
X X X X
X X X X
X O X X

    A board with a single 'O' keeps it, because that cell is on every edge.

    Approach: start from the edge

    The direct approach asks, for each 'O', whether some path of 'O' cells leads to the edge. That can repeat a lot of work: one large region in the middle of the board gets searched again from each of its cells, which can cost about (m · n)² in total.

    The lesson turns the question around. Every 'O' on the edge is safe, and so is every 'O' connected to a safe one. So a breadth-first search (BFS) starts from all the edge 'O' cells at once and marks every cell it reaches as safe. Afterwards, any 'O' that is not marked is surrounded, and one more pass over the board turns it into 'X'.

    The search uses a queue instead of recursion. A single region can wind through the whole board, and a recursive search that goes tens of thousands of calls deep is a risk. A queue also needs no extra function.

    The third example shows why the search must follow only the four directions. The board is

    O X X X X
X O O O X
X X X O X
X O X O X
X X X O X

    The middle region winds down to the 'O' in the last row, so none of it is captured. The 'O' in the top-left corner touches that region only diagonally, but it is on the edge itself. The 'O' at row 3, column 1 is closed in on all four sides and becomes 'X'. The board does not change, apart from that one cell.

    Step by step

    1. Read the size. rows is len(board) and cols is len(board[0]), since all rows have the same length.
    2. Create safe with make([][]bool, rows). It marks the cells connected to the edge. This only makes the outer slice, and each row is made in the loop.
    3. Create the queue as [][2]int{}, a slice of row and column pairs. It holds the safe cells whose neighbours are still to be checked.
    4. Loop over the rows and, inside it, create safe[r] as make([]bool, cols), which starts as all false.
    5. Loop over the columns. For each cell, compute onBorder: row 0, last row, column 0 or last column, joined with ||.
    6. Seed the search. For a cell with onBorder && board[r][c] == 'O', set safe[r][c] to true and append [2]int{r, c} to the queue. Marking the cell as it joins the queue keeps it from being added twice.
    7. Define directions: up, down, left and right as {row change, column change} pairs.
    8. Run the BFS with for len(queue) > 0. Take the front cell and drop it with queue = queue[1:], then unpack row, col := cell[0], cell[1].
    9. Check each neighbour. Compute nextRow and nextCol, and make sure they are inside the board before indexing with them.
    10. Spread to 'O' neighbours that are not yet marked: set them safe and append them to the queue.
    11. Capture. A second pass over the board turns every 'O' that is not safe into 'X'.

    The solution in Go

    func solve(board [][]byte) {
    rows := len(board)
    cols := len(board[0])
    safe := make([][]bool, rows)
    queue := [][2]int{}
    for r := 0; r < rows; r++ {
        safe[r] = make([]bool, cols)
        for c := 0; c < cols; c++ {
            onBorder := r == 0 || r == rows - 1 || c == 0 || c == cols - 1
            if onBorder && board[r][c] == 'O' {
                safe[r][c] = true
                queue = append(queue, [2]int{r, c})
            }
        }
    }
    directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    for len(queue) > 0 {
        cell := queue[0]
        queue = queue[1:]
        row, col := cell[0], cell[1]
        for _, d := range directions {
            nextRow := row + d[0]
            nextCol := col + d[1]
            if nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols {
                if board[nextRow][nextCol] == 'O' && !safe[nextRow][nextCol] {
                    safe[nextRow][nextCol] = true
                    queue = append(queue, [2]int{nextRow, nextCol})
                }
            }
        }
    }
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if board[r][c] == 'O' && !safe[r][c] {
                board[r][c] = 'X'
            }
        }
    }
}

    The Go details worth a closer look:

    • Bytes and quotes. Each cell is a byte, and 'O' in single quotes is the letter's code, so board[r][c] == 'O' compares directly. Double quotes would make a string, which can't be compared with a byte.
    • A slice of slices. make([][]bool, rows) creates rows nil rows. Each one needs its own make, which the first loop does before any cell of that row is read.
    • Pairs as arrays. [2]int is an array of exactly two integers. Unlike a slice, it is a value, so cell is a copy of the pair in the queue.
    • The queue is a slice. append adds at the back and queue[1:] drops the front without copying the rest.
    • Changing the board in place. A slice header is copied when passed to a function, but it points at the same rows, so writing board[r][c] = 'X' changes the caller's grid. That is why the function needs no return value.
    • The bounds check comes first. Indexing board[nextRow][nextCol] with a negative value or one past the end panics, so the position is tested before it is used.

    Complexity

    Time: O(m · n). The first pass visits each cell once. Each cell joins the queue at most once, because it is marked as it joins, and each cell taken from the queue looks at four neighbours. The last pass visits each cell once.

    Space: O(m · n). The safe grid has one entry per cell, and the queue holds at most every cell once.

    Edge cases and common mistakes

    • Single cell. A board holding just O stays O. A board with just X has nothing to change.
    • Every cell on the edge. Any board with fewer than three rows or three columns has no cell off the edge, so it never changes. O X O O stays the same.
    • All 'O'. A 3 × 3 board of O cells keeps every cell, since the middle one is connected to the edge.
    • A lone inner 'O'. In a 3 × 3 board of X cells with an O in the middle, the middle becomes X.
    • Looking only at the edge cells. Capturing every interior 'O' without spreading from the edge is wrong. On the third example it turns the winding region into X and leaves only the two cells on the edge: 
      O X X X X
X X X X X
X X X X X
X X X X X
X X X O X
    • Counting diagonals. A search that also steps diagonally connects the region in the first example to the edge 'O' in the last row, so nothing is captured there. The expected result needs the four directions only.
    • Large regions. A 200 × 200 board whose inner 198 × 198 block is all O is captured entirely, and if one edge cell is an O that touches the block, all 39,205 O cells stay. The queue handles this without recursion.

    Testing

    • The first example board becomes all X except the O at row 3, column 1.
    • A board with one O keeps it.
    • The third example changes only the O at row 3, column 1.
    • O X O O (one row) is unchanged.
    • A 3 × 3 board with O in the middle and X elsewhere becomes all X.
    Keep going with Go500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free