Start learning free

LESSON 505 OF 573 · GRAPHS

Surrounded Regions in Kotlin: BFS from the Border in O(m·n)

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

    KOTLIN · GRAPHS

    Surrounded Regions in Kotlin, explained

    Problem overview

    The method solve receives board, a grid of m rows and n columns of Char values, each 'X' or 'O'. It returns nothing: it must change board itself.

    Two 'O' cells are connected when they touch side by side (up, down, left or right, never diagonally). A region is a group of connected 'O' cells. A region is surrounded when none of its cells lies on the border of the board, which means the first or last row, or the first or last column. Every surrounded region is captured: all its cells become 'X'. A region with at least one cell on the border stays as it is.

    In the lesson's first example, the board has three 'O' cells in the middle that form one region, and none of them is on the border, so they are captured. The 'O' in the last row stays. The board X X X X / X O O X / X X O X / X O X X becomes X X X X / X X X X / X X X X / X O X X.

    Approach: find what is safe, capture the rest

    The direct idea is to take each 'O' and search outward to see whether its region reaches the border. That repeats the same search many times: one big region in the middle of the board gets searched again from each of its cells, which can cost time quadratic in the number of cells.

    Turn the question around. Every 'O' on the border is safe, and so is every 'O' connected to a safe one. So start from all the border 'O' cells at once and spread inward with a breadth-first search, marking every 'O' reached. When the search ends, the marked cells are exactly the cells of the regions that touch the border. Any 'O' still unmarked belongs to a surrounded region, and one more pass over the board turns it into 'X'.

    Marking a cell as soon as it joins the queue, not when it leaves, means no cell is queued twice, so every cell is processed at most once.

    The search uses a queue instead of recursion on purpose. A single region can wind through the whole board, and a recursive search that goes tens of thousands of calls deep can overflow the call stack. The queue lives on the heap and has no such limit.

    Step by step

    1. Read the size. rows is board.size and cols is board[0].size. All rows have the same length.
    2. Create safe, a grid of booleans with the same shape as the board. A cell is marked true when it holds an 'O' connected to the border. Nothing is marked at the start.
    3. Create queue, a queue of Pair<Int, Int> values holding (row, column) positions of safe cells whose neighbours still have to be checked.
    4. Loop over the rows and, inside, the columns to find the border cells.
    5. Compute onBorder with four tests joined by ||: first row, last row, first column or last column.
    6. Seed the queue. When the cell is on the border and holds an 'O', mark it in safe and add its position to the queue.
    7. Define directions, the four moves: up, down, left, right. No move changes both the row and the column, so diagonal cells are never neighbours.
    8. Run the search while the queue is not empty. Take the position at the front and unpack it into row and col.
    9. Try each direction. Compute nextRow and nextCol.
    10. Check bounds. A border cell has neighbours outside the board, and those are skipped.
    11. Spread. If the neighbour holds an 'O' and is not yet marked, mark it and add its position to the queue.
    12. Capture. After the search, go over the board again. Every 'O' that is not marked safe becomes 'X'.

    The solution in Kotlin

    class Solution {
    fun solve(board: Array<CharArray>) {
        val rows = board.size
        val cols = board[0].size
        val safe = Array(rows) { BooleanArray(cols) }
        val queue = ArrayDeque<Pair<Int, Int>>()
        for (r in 0 until rows) {
            for (c in 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.add(Pair(r, c))
                }
            }
        }
        val directions = arrayOf(Pair(-1, 0), Pair(1, 0), Pair(0, -1), Pair(0, 1))
        while (queue.isNotEmpty()) {
            val (row, col) = queue.removeFirst()
            for ((dr, dc) in 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.add(Pair(nextRow, nextCol))
                    }
                }
            }
        }
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (board[r][c] == 'O' && !safe[r][c]) {
                    board[r][c] = 'X'
                }
            }
        }
    }
}

    Kotlin details worth knowing:

    • The board is modified in place. Array<CharArray> is a mutable array of mutable rows, passed by reference. Assigning board[r][c] = 'X' changes the caller's board, which is why the method needs no return value.
    • Chars use single quotes. 'O' is a Char, and each cell of a CharArray is one.
    • Building safe. Array(rows) { BooleanArray(cols) } runs the block once per row, so each row is a separate array. Writing Array(rows, BooleanArray(cols)) instead does not compile: argument type mismatch: actual type is 'BooleanArray', but 'Function1<Int, T (of class Array<T>)>' was expected. A new BooleanArray starts all false.
    • Destructuring. A Pair can be unpacked, as in val (row, col) = queue.removeFirst() and for ((dr, dc) in directions). Both give each half of the pair its own name.
    • ArrayDeque is Kotlin's own deque: add puts an element at the back and removeFirst() takes one from the front, both in constant time.

    Complexity

    Time: O(m · n). The first pass visits each cell once. Each cell joins the queue at most once, because it is marked when added, and 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 can hold a large part of the board at once.

    Edge cases and common mistakes

    • One cell. A board holding just O stays O: the cell is on every border. A board X X X / X O X / X X X becomes all X.
    • A board of only 'O'. A 3 by 3 board of 'O' cells stays unchanged: the whole board is one region, and it touches the border.
    • Diagonal contact doesn't connect. In the lesson's third example, the 'O' in the top-left corner touches the middle region only diagonally. It is on the border anyway, so it stays. On the board X O X / O X O / X O X, the four 'O' cells touch each other only diagonally, and each is on the border, so nothing changes.
    • Only keeping border cells. Checking only whether a cell is on the border, without spreading, changes the lesson's third example into 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. The middle cells of the region that reaches the border are wrongly captured, because they are not on the border themselves. The search has to follow the connections.
    • Large regions. A 200 by 200 board that is all 'O' stays unchanged, and a long winding region in the middle of a 200 by 200 board is captured completely when it is closed (all 19,701 of its cells in a test), or kept completely when a single cell of it touches the border.

    Testing

    • X X X X / X O O X / X X O X / X O X X becomes X X X X / X X X X / X X X X / X O X X.
    • O stays O.
    • 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 becomes 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.
    • X X X X X / X O O O X / X O X O X / X O O O X / X X X X X, a ring of 'O' cells, becomes all X.
    • O O O / O O O / O O O stays unchanged.
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free