Start learning free

LESSON 501 OF 569 · GRAPHS

Surrounded Regions in Java: BFS from the Edge

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 22
    Ctrl + Enter to check

    JAVA · GRAPHS

    Surrounded Regions in Java, explained

    Problem overview

    The method solve receives board, a char[][] of m rows and n columns where every cell is 'X' or 'O'. Two 'O' cells are connected when they are side by side (up, down, left or right, never diagonal). 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. Every surrounded region must be captured: all its cells become 'X'. A region that touches the edge stays as it is. The method returns nothing; board itself must hold the result.

    In the first example, the three 'O' cells in the middle form one region with no cell on the edge, so they become 'X', while the 'O' in the last row is on the edge and stays:

    before   after
XXXX     XXXX
XOOX     XXXX
XXOX     XXXX
XOXX     XOXX

    A board with a single 'O' keeps it: that cell is on every edge. In the bigger third example, a long region winds down to the last row, so none of it is captured, and the 'O' in the top-left corner stays because it is on the edge itself. Only the lone 'O' in row 3, column 1 has 'X' on all four sides and is captured.

    Approach: start from the edge

    The direct idea is to take each 'O' and search for a path of 'O' cells to the edge. That can repeat the same work many times: one large region in the middle of the board is searched again from each of its cells, which in the worst case costs on the order of (m · n)² steps.

    Turn the question around. Every 'O' on the edge is safe. So is every 'O' connected to a safe one. Start a breadth-first search (BFS) from all the edge 'O' cells at once, and mark every cell it reaches as safe. When the search ends, any 'O' that was never marked has no path of 'O' cells to the edge, so its region is surrounded. One more pass turns those cells into 'X'.

    A cell is marked when it joins the queue, not when it leaves it, so it enters the queue at most once. The search uses a queue, not recursion: a single region can snake through the whole board, and a recursive search that deep could exhaust the call stack. With a queue the depth of the search does not matter.

    Step by step

    1. Store the dimensions. rows is board.length, and cols is board[0].length, since all rows have the same length.
    2. Create safe, a boolean[][] of the same size. Java fills it with false, which means "not reached yet".
    3. Create the queue as an ArrayDeque declared as Deque<int[]>. Each entry is a two-element array: row and column.
    4. Loop over the rows and the columns with two nested for loops to find the edge cells.
    5. Compute onBorder: the row is first or last, or the column is first or last, joined with ||.
    6. Check for an edge 'O' with onBorder && board[r][c] == 'O'. The single quotes make 'O' a char, the type of each cell.
    7. Mark it in safe and queue it with new int[]{r, c}.
    8. Define the four moves as {row change, column change} pairs: up, down, left and right. Each changes only one coordinate, so diagonal cells are never neighbours.
    9. Loop while the queue is not empty. Each turn takes one safe cell and checks its neighbours.
    10. Take a cell with poll and read its row and column.
    11. Go over the moves and compute nextRow and nextCol.
    12. Check the neighbour is on the board. Cells on the edge have neighbours outside it, and those are skipped before indexing.
    13. If the neighbour is an unmarked 'O', mark it and queue it. An 'O' next to a safe one is in the same region and so is connected to the edge too.
    14. After the search, loop over the board again and set every 'O' that is not safe to 'X'.

    The solution in Java

    class Solution {
    public void solve(char[][] board) {
        int rows = board.length;
        int cols = board[0].length;
        boolean[][] safe = new boolean[rows][cols];
        Deque<int[]> queue = new ArrayDeque<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                boolean onBorder = r == 0 || r == rows - 1 || c == 0 || c == cols - 1;
                if (onBorder && board[r][c] == 'O') {
                    safe[r][c] = true;
                    queue.add(new int[]{r, c});
                }
            }
        }
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0];
            int col = cell[1];
            for (int[] d : directions) {
                int nextRow = row + d[0];
                int 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.add(new int[]{nextRow, nextCol});
                    }
                }
            }
        }
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (board[r][c] == 'O' && !safe[r][c]) {
                    board[r][c] = 'X';
                }
            }
        }
    }
}

    Java details: board is an array of char arrays, so assigning board[r][c] = 'X' changes the caller's board; this is why the method can be void. The boolean[][] needs no filling, because new arrays hold false. poll() returns the front element and removes it. The method uses && and ||, which stop evaluating as soon as the result is known, and the bounds test comes before board[nextRow][nextCol], so an off-board index is never read.

    Complexity

    Each cell enters the queue at most once and looks at four neighbours, and the two passes over the board visit each cell once, so the time is O(m · n). The safe array and the queue take O(m · n) extra space.

    The queue approach does not depend on region shape. On a 200 by 200 board with a frame of 'X' around a 198 by 198 block of 'O', the whole block is captured; on a 200 by 200 board of only 'O', every cell is on or connected to the edge and all 40000 stay.

    Edge cases and common mistakes

    • Treating every non-edge 'O' as captured. That ignores connectivity. On the third example it leaves only the corner and one more 'O' instead of keeping the whole winding region: 
      OXXXX
XXXXX
XXXXX
XXXXX
XXXOX
    • Diagonal neighbours. In XOX / OXO / XOX no 'O' is connected to another, and all four are on the edge, so the board does not change.
    • A board with no edge 'O'. A single 'O' inside an 'X' frame (XXX / XOX / XXX) is captured.
    • Marking on removal from the queue. A cell could then be queued several times by different neighbours. Marking on insertion avoids it.
    • Checking bounds after indexing. Reading board[nextRow][nextCol] before the bounds test throws ArrayIndexOutOfBoundsException on the edges.
    • Recursion on large boards. A deep recursive search may overflow the stack; the queue does not.

    Testing

    Run against the solution above, these boards, written row by row, give:

    BoardResult
    XXXX / XOOX / XXOX / XOXXXXXX / XXXX / XXXX / XOXX
    OO
    OXXXX / XOOOX / XXXOX / XOXOX / XXXOXOXXXX / XOOOX / XXXOX / XXXOX / XXXOX
    OOO / OXO / OOOunchanged
    XXX / XOX / XXXXXX / XXX / XXX
    XOX / OXO / XOXunchanged
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free