Start learning free

LESSON 506 OF 574 · GRAPHS

Surrounded Regions in Swift: 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 23
    Ctrl + Enter to check

    SWIFT · GRAPHS

    Surrounded Regions in Swift, explained

    Problem overview

    The method solve receives board, a grid of m rows and n columns made of the characters "X" and "O", as an array of rows of Character values. 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 "O" cells connected to each other and to no other "O".

    A region is surrounded when none of its cells lies on the edge of the board (first or last row, first or last column). The method must change every cell of every surrounded region to "X". A region with a cell on the edge stays as it is. The board is changed in place and nothing is returned: the parameter is inout [[Character]].

    Take this board:

    XXXX
XOOX
XXOX
XOXX

    The three cells (1,1), (1,2) and (2,2) form one region and none of them is on the edge, so they are captured. The "O" at (3,1) is in the last row, so it stays. The board becomes:

    XXXX
XXXX
XXXX
XOXX

    Approach: start from the edge and mark what is safe

    The direct approach checks each "O" region for a path to the edge. A big region in the middle of the board would be searched again from every one of its cells, which can cost O((m · n)^2).

    The idea is to turn the question around. Every "O" on the edge is safe, and so is every "O" connected to a safe one, because they belong to the same region. A breadth-first search that starts from all the edge "O"s at once marks every safe cell, and each cell enters the queue at most once. After it, every "O" that is not marked has no path of "O"s to the edge, so its region is surrounded, and one more pass over the board turns it into "X".

    A queue is used instead of recursion. A region can wind through the whole board, and a recursive search that goes tens of thousands of calls deep can run out of call stack.

    A tempting shortcut is to flip every "O" that is not itself on the edge. On this board:

    OXXXX
XOOOX
XXXOX
XOXOX
XXXOX

    it would leave only the corner "O" and the last "O" of the bottom row and capture the whole middle region, even though that region reaches the last row through its bottom cell. The correct result keeps all of it:

    OXXXX
XOOOX
XXXOX
XXXOX
XXXOX

    Only the lone "O" at (3,1) is closed in on all four sides, so it becomes "X". The corner "O" touches the middle region only diagonally, but it is on the edge itself.

    Step by step

    1. Read the size. Store board.count in rows and board[0].count in cols. Every row has the same length.
    2. Create safe, a grid of false values of the same size, by repeating a row of cols falses rows times. A cell is marked true when it holds an "O" connected to the edge.
    3. Create queue, an empty array of (Int, Int) tuples. It holds the safe cells whose neighbours are still to be checked.
    4. Loop over the rows with r and, inside, over the columns with c. This first pass finds the "O"s on the edge.
    5. Test for the edge. The constant onBorder is true when r == 0, r == rows - 1, c == 0 or c == cols - 1.
    6. Start from edge "O"s. When onBorder && board[r][c] == "O", set safe[r][c] to true and append (r, c) to queue. A cell is marked as it joins the queue, so no other cell adds it a second time.
    7. Define the four moves in directions: up (-1, 0), down (1, 0), left (0, -1), right (0, 1). Each move changes only one coordinate, so diagonals are never neighbours.
    8. Create head, starting at 0: the index of the next cell to take from the queue. Moving it forward takes a cell out of the queue without shifting the others, which removeFirst() would do.
    9. Loop while head < queue.count. Each turn takes one safe cell and checks its four neighbours.
    10. Take the cell: unpack queue[head] into (row, col) and do head += 1.
    11. Loop over directions, unpacking each move into (dr, dc), and compute nextRow and nextCol.
    12. Stay inside the board. Check that both coordinates are at least 0 and below rows or cols before indexing with them.
    13. Spread the mark. If the neighbour holds "O" and is not safe yet, set it safe and append it to the queue.
    14. Capture. After the search, loop over the whole board again. Every cell that holds "O" and is not safe is set to "X".

    The solution in Swift

    class Solution {
    func solve(_ board: inout [[Character]]) {
        let rows = board.count
        let cols = board[0].count
        var safe = [[Bool]](repeating: [Bool](repeating: false, count: cols), count: rows)
        var queue = [(Int, Int)]()
        for r in 0..<rows {
            for c in 0..<cols {
                let onBorder = r == 0 || r == rows - 1 || c == 0 || c == cols - 1
                if onBorder && board[r][c] == "O" {
                    safe[r][c] = true
                    queue.append((r, c))
                }
            }
        }
        let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        var head = 0
        while head < queue.count {
            let (row, col) = queue[head]
            head += 1
            for (dr, dc) in directions {
                let nextRow = row + dr
                let 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.append((nextRow, nextCol))
                    }
                }
            }
        }
        for r in 0..<rows {
            for c in 0..<cols {
                if board[r][c] == "O" && !safe[r][c] {
                    board[r][c] = "X"
                }
            }
        }
    }
}

    The Swift details worth a closer look:

    • inout. Parameters are constants and arrays are copied when passed. An inout parameter lets solve change the caller's board, which is why the method returns nothing. To call it, the caller writes solution.solve(&grid) with a var grid.
    • Characters. The cells are Character values. A double-quoted literal such as "O" becomes a Character when it is compared with a cell or assigned to one.
    • Independent rows. [[Bool]](repeating: [Bool](repeating: false, count: cols), count: rows) repeats one row, but arrays are value types, so each row is its own copy and marking one cell changes only that row. In a language where arrays are references, the same trick would share one row.
    • Tuples. queue holds (Int, Int) pairs. let (row, col) = queue[head] and for (dr, dc) in directions unpack them directly.
    • The nested if. The bounds check has to come first. The neighbour is read with board[nextRow][nextCol] only inside it, because an index outside the array stops the program at run time in Swift.

    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 it joins, and it looks at 4 neighbours when it leaves. The last pass visits each cell once.

    Space: O(m · n). The safe grid has one entry per cell, and the queue can hold up to every cell of the board.

    Edge cases and common mistakes

    • A single cell. The board ["O"] has one cell that is on every edge, so it stays "O".
    • Thin boards. When a board has one or two rows or columns, every cell is on the edge, so nothing is captured.
    • A ring around an "X". The board OOO / OXO / OOO is unchanged: every "O" is on the edge.
    • A lone interior "O". The board XXX / XOX / XXX becomes all "X".
    • Diagonal neighbours. Adding diagonal moves to directions would join cells that the problem keeps apart: two "O"s that only touch at a corner are not connected.
    • Checking only edge cells. An "O" next to the edge is not safe on its own. Safety spreads through connected "O"s, which is why a search is needed.
    • Marking when taken out. If a cell is marked only when it leaves the queue, it can be appended several times by different neighbours. Mark it as it joins.
    • Bounds. Checking nextRow < rows and nextCol < cols but forgetting the lower bounds of 0 crashes on cells in the first row or column.

    Testing

    • XXXX / XOOX / XXOX / XOXX becomes XXXX / XXXX / XXXX / XOXX.
    • O stays O.
    • OXXXX / XOOOX / XXXOX / XOXOX / XXXOX becomes OXXXX / XOOOX / XXXOX / XXXOX / XXXOX.
    • XXX / XOX / XXX becomes XXX / XXX / XXX.
    • OOO / OXO / OOO stays the same.
    Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free