Start learning free

LESSON 505 OF 573 · GRAPHS

Surrounded Regions in Scala: Multi-Source 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 21
    Ctrl + Enter to check

    SCALA · GRAPHS

    Surrounded Regions in Scala, explained

    Problem overview

    The method solve receives board, an Array[Array[Char]] grid of m rows and n columns. Every cell is 'X' or 'O'. Two 'O' cells are connected when one is directly above, below, left or right of the other; diagonals don't count. A group of connected 'O' cells is a region.

    A region is surrounded when none of its cells is on the edge of the board, that is, in the first or last row or the first or last column. The method must change every cell of every surrounded region to 'X'. A region with at least one cell on the edge stays as it is. The method returns Unit: the change is made in board itself.

    Here is a board with 5 rows and 5 columns, and the same board after solve:

    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
    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

    The region in the middle winds down to the 'O' in the last row, so it touches the edge and survives. The 'O' in the top-left corner is on the edge itself. The 'O' in row 3, column 1 is closed in by 'X' on all four sides, so it becomes 'X'.

    Approach: start from the edge instead of from each region

    The direct way is to take each 'O' and search for a path of 'O' cells to the edge. That repeats work: one big region in the middle of the board is searched again from each of its cells, which can cost O((m * n)^2).

    Turning the question around fixes it. An 'O' on the edge is safe, and so is every 'O' connected to a safe one. One breadth-first search that starts from all the border 'O' cells at once marks every safe cell, and each cell enters the queue at most once. An 'O' that was never marked has no path of 'O' cells to the edge, so its region is surrounded. A second pass over the board turns those cells into 'X'.

    The search uses a queue rather than recursion. One region can wind through the whole board, and a recursive search that deep can exhaust the call stack.

    Step by step

    1. Read the size: rows is board.length and cols is board(0).length. Every row has the same length.
    2. Create safe with Array.fill(rows, cols)(false): a grid of booleans, all false. A cell becomes true when it holds an 'O' connected to the edge.
    3. Create queue, an empty mutable.Queue[(Int, Int)]() of (row, column) tuples.
    4. Loop over the rows with r <- 0 until rows.
    5. Loop over the columns inside it with c <- 0 until cols.
    6. Test for the edge: onBorder is true when r is the first or last row, or c is the first or last column.
    7. Find the border 'O' cells: if (onBorder && board(r)(c) == 'O').
    8. Mark the cell safe. Marking it as it joins the queue means no other cell can add it a second time.
    9. Enqueue (r, c). Its neighbours are checked when it leaves the queue.
    10. Define directions as the four moves: up, down, left, right. Each changes the row or the column by one, never both.
    11. Loop while queue.nonEmpty.
    12. Dequeue a cell and unpack it into val (row, col).
    13. Loop over directions with (dr, dc) <- directions.
    14. Compute the neighbour: nextRow and nextCol.
    15. Check the bounds before using them as indexes. Cells on the edge have neighbours outside the board.
    16. Test the neighbour: it must hold 'O' and not be marked yet. An 'O' next to a safe one is in the same region, so it is safe too.
    17. Mark it safe.
    18. Enqueue it.
    19. Second pass: loop r over 0 until rows.
    20. Inner loop: c over 0 until cols.
    21. Capture: if board(r)(c) == 'O' && !safe(r)(c), set the cell to 'X'.

    The solution in Scala

    class Solution {
    def solve(board: Array[Array[Char]]): Unit = {
        val rows = board.length
        val cols = board(0).length
        val safe = Array.fill(rows, cols)(false)
        val queue = mutable.Queue[(Int, Int)]()
        for (r <- 0 until rows) {
            for (c <- 0 until cols) {
                val onBorder = r == 0 || r == rows - 1 || c == 0 || c == cols - 1
                if (onBorder && board(r)(c) == 'O') {
                    safe(r)(c) = true
                    queue.enqueue((r, c))
                }
            }
        }
        val directions = Array((-1, 0), (1, 0), (0, -1), (0, 1))
        while (queue.nonEmpty) {
            val (row, col) = queue.dequeue()
            for ((dr, dc) <- directions) {
                val nextRow = row + dr
                val nextCol = col + dc
                if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
                    if (board(nextRow)(nextCol) == 'O' && !safe(nextRow)(nextCol)) {
                        safe(nextRow)(nextCol) = true
                        queue.enqueue((nextRow, nextCol))
                    }
                }
            }
        }
        for (r <- 0 until rows) {
            for (c <- 0 until cols) {
                if (board(r)(c) == 'O' && !safe(r)(c)) {
                    board(r)(c) = 'X'
                }
            }
        }
    }
}

    Scala details worth a look:

    • Chars use single quotes. 'O' is a Char, the type of each cell. "O" would be a String, and Scala 3 refuses to compare the two: the compiler reports "Values of types Char and String cannot be compared with == or !=".
    • Two sets of parentheses. board(r)(c) reads the row r, then the cell c of that row. Assignment works the same way: board(r)(c) = 'X' changes the array in place.
    • Tuple patterns. val (row, col) = queue.dequeue() unpacks the tuple. The same pattern works in a for: for ((dr, dc) <- directions).
    • Array.fill(rows, cols)(false) builds a two-dimensional array of booleans. Unlike board, safe is a separate array of our own, so the search can mark cells without changing the board.
    • No return value. A method declared with : Unit = ends with the loops, and callers read the result from the array they passed in.

    Complexity

    Time: O(m * n). The first pass visits every cell once. Each cell joins the queue at most once and checks four neighbours. The last pass visits every cell once.

    Space: O(m * n). The safe grid has one entry per cell, and the queue can hold a good share of the cells at once.

    Edge cases and common mistakes

    • A one-cell board. O stays O: the only cell is on every edge. X stays X.
    • Keeping only the border cells. A version that turns every 'O' that is not on the edge into 'X', without spreading from the border, wrecks the 5 by 5 board above: the middle region is captured even though it reaches the last row. The result keeps only the border cells (shown below the list).
    • Diagonal neighbours. Only four directions connect cells. The corner 'O' in the example touches the middle region only diagonally; it is safe because it is on the edge itself.
    • A board with no 'O' on the edge. XXX / XOX / XXX (three rows) becomes all X.
    • A ring of 'O' cells around an 'X'. OOO / OXO / OOO stays unchanged: the ring is 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

    Cells that connect to the edge through other 'O' cells must be kept as well, which is why the search spreads from the border.

    Testing

    • Rows XXXX, XOOX, XXOX, XOXX become XXXX, XXXX, XXXX, XOXX.
    • A board holding just O stays O.
    • Rows XXX, XOX, XXX become all X.
    • Rows OOO, OXO, OOO stay the same.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free