Start learning free

LESSON 508 OF 576 · GRAPHS

Surrounded Regions in Rust: BFS from the Edge 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

    RUST · GRAPHS

    Surrounded Regions in Rust, explained

    Problem overview

    The function solve receives board, a &mut Vec<Vec<char>>: a grid of m rows and n columns in which every cell holds 'X' or 'O'. Two 'O' cells are connected when one is directly above, below, left or right of the other. Diagonal neighbours do not count. A region is a group of 'O' cells that reach each other through connected 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 at least one 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 at the top form one region with no cell on the edge, so they become 'X'. 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

    The statement asks for O(m * n) time and O(m * n) extra space.

    Approach: start from the edge, not from the regions

    The obvious question is "does this region reach the edge?", asked once per region. A cell-by-cell version of that question can search the same large region again from each of its cells, which can cost O((m * n)^2). Capturing every interior 'O' without searching is wrong as well. On this 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

    a version that turns every 'O' not on the edge into 'X' returns

    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

    which wrongly captures the winding region in the middle: it reaches the edge through the 'O' in the last row. Only the 'O's on the edge survive.

    The way out is to turn the question around. Every 'O' on the edge is safe, and so is every 'O' connected to a safe one. So begin with all the edge 'O's at once and spread inward with a breadth-first search (BFS), marking every cell it reaches. Each cell joins the queue at most once. When the search ends, 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 those cells into 'X'.

    On the board above, the edge pass queues the two edge cells (0, 0) and (4, 3), and the search then marks the middle region, one cell at a time. The marked cells, shown as S, are:

    S....
.SSS.
...S.
...S.
...S.

    The one unmarked 'O', at row 3, column 1, is the surrounded cell. It becomes 'X', and the result is

    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 lesson uses a queue rather than recursion, because a single region can wind through the whole board, and a recursive search that deep can run out of call stack.

    Step by step

    1. Read the size. rows is board.len() and cols is board[0].len(). All rows have the same length.
    2. Create the safe grid with vec![vec![false; cols]; rows]. The inner vec! makes one row, and the outer one repeats it rows times, each with its own copy. At the start nothing is marked.
    3. Create the queue as a VecDeque<(usize, usize)>. It holds the safe cells whose neighbours are still to be checked, as (row, column) tuples.
    4. Loop over rows and columns with two nested for loops, to find the 'O' cells on the edge.
    5. Test for the edge. on_border is true for the first or last row or the first or last column, joined with ||.
    6. Seed the search. If the cell is on the edge and holds an 'O', set safe[r][c] to true and push_back((r, c)). Marking at the moment of queueing means no other cell can add it a second time.
    7. Describe the four moves as an array of (row change, column change) tuples of type [(i32, i32); 4]. They are i32 because a move can be negative.
    8. Run the search with while let Some((row, col)) = queue.pop_front(). It ends when the queue is empty.
    9. Visit each neighbour. Loop over &directions with the pattern &(dr, dc), which copies the two numbers out of the array.
    10. Compute the neighbour in i32: next_row = row as i32 + dr and next_col = col as i32 + dc.
    11. Check that it is on the board: both values at least 0 and below rows as i32 or cols as i32. In i32, a step off the top or the left edge shows up as -1, which the check can see.
    12. Convert back to indexes with as usize, shadowing the two names in one tuple.
    13. Mark and queue the neighbour if it holds an 'O' and is not marked yet: set safe to true and push it.
    14. Capture. After the search, loop over the board again and turn each 'O' that is not marked safe into 'X'.

    The solution in Rust

    use std::collections::VecDeque;

impl Solution {
    fn solve(board: &mut Vec<Vec<char>>) {
        let rows = board.len();
        let cols = board[0].len();
        let mut safe = vec![vec![false; cols]; rows];
        let mut queue: VecDeque<(usize, usize)> = VecDeque::new();
        for r in 0..rows {
            for c in 0..cols {
                let on_border = r == 0 || r == rows - 1 || c == 0 || c == cols - 1;
                if on_border && board[r][c] == 'O' {
                    safe[r][c] = true;
                    queue.push_back((r, c));
                }
            }
        }
        let directions: [(i32, i32); 4] = [(-1, 0), (1, 0), (0, -1), (0, 1)];
        while let Some((row, col)) = queue.pop_front() {
            for &(dr, dc) in &directions {
                let next_row = row as i32 + dr;
                let next_col = col as i32 + dc;
                if next_row >= 0 && next_row < rows as i32 && next_col >= 0 && next_col < cols as i32 {
                    let (next_row, next_col) = (next_row as usize, next_col as usize);
                    if board[next_row][next_col] == 'O' && !safe[next_row][next_col] {
                        safe[next_row][next_col] = true;
                        queue.push_back((next_row, next_col));
                    }
                }
            }
        }
        for r in 0..rows {
            for c in 0..cols {
                if board[r][c] == 'O' && !safe[r][c] {
                    board[r][c] = 'X';
                }
            }
        }
    }
}

    The Rust details worth a closer look:

    • &mut Vec<Vec<char>>. The function borrows the caller's board mutably. It changes the cells through the borrow, so the caller sees the result without anything being returned. Each cell is a char, written with single quotes: 'O' is a char, while "O" would be a string.
    • Casting for the bounds check. A usize cannot be negative. In a build with overflow checks, row - 1 at row 0 panics, and in the optimized build the lessons use it wraps to a huge number. Converting to i32 first makes -1 a normal value that the range check can reject, and as usize runs only after the check has passed.
    • Shadowing. let (next_row, next_col) = (next_row as usize, next_col as usize); reuses the names for new variables of the index type, so the code below reads naturally.
    • The pattern &(dr, dc). Iterating &directions yields references to tuples. The & in the pattern copies the two i32 values out, so dr and dc are plain numbers.
    • while let. pop_front() returns an Option, and the loop runs as long as it matches Some(...). The tuple is unpacked into row and col.
    • The grid of flags. The inner vec![false; cols] is cloned by the outer vec![...; rows], so the rows do not share storage.
    • Edge-of-board indexes. rows - 1 and cols - 1 are safe because the constraints guarantee at least one row and one column.

    Complexity

    Time: O(m * n). The edge pass and the final pass each visit every cell once. Each cell joins the queue at most once and checks four neighbours with constant work.

    Space: O(m * n). The safe grid has one flag per cell, and the queue holds at most all the cells.

    Edge cases and common mistakes

    • A single cell. The board O has its only cell on every edge, so it stays O. A one-row board such as O O O is entirely on the edge and nothing is captured.
    • An isolated interior cell. A 3 x 3 board with O in the middle and X around it becomes all X.
    • Capturing every interior 'O'. It ignores the connection to the edge, as the board above shows.
    • Counting diagonals as connections. With eight directions instead of four, on the board O X X X X / X O X X X / X X X X X the interior 'O' would stay, because it touches the edge 'O' diagonally. The correct result turns it into 'X'.
    • Edge 'O's that are not connected to each other. Seeding the queue with all of them is what makes the search start from every edge at once, not from one corner.
    • Marking when popping instead of when pushing. A cell could then join the queue several times before it is processed. The flag set before push_back prevents that.
    • Recursive search. A single region can wind through a board of up to 200 x 200 cells, which makes a recursive version very deep. The queue keeps the depth out of the call stack.

    Testing

    • The board XXXX / XOOX / XXOX / XOXX becomes XXXX / XXXX / XXXX / XOXX.
    • The board O stays O.
    • The board OXXXX / XOOOX / XXXOX / XOXOX / XXXOX becomes OXXXX / XOOOX / XXXOX / XXXOX / XXXOX.
    • The board XOX / OXO / XOX stays the same: each 'O' is on the edge.
    • The board XXX / XOX / XXX becomes all X.
    • The board XXXXX / XOOOX / XOXOX / XOOOX / XXXXX becomes all X: the ring of 'O's is one surrounded region.
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free