Surrounded Regions

The problem

You are given board, a grid in which every cell holds the letter X or the letter O. A region is an O cell together with every O cell you can reach from it by stepping up, down, left or right over O cells. Cells that touch only at a corner are not joined. A region is surrounded when none of its cells lies on an edge of the board. Change every O of every surrounded region to X and leave all other cells as they are. Return the board: you may change board itself and return it.

What to write

function solve(board: string[][]): string[][]

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

Input
board = [["O"]]

Output
[["O"]]

Constraints

Modify and return the board for this local runner; it contains only O and X.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   An O on an edge of the board can never be captured (changed to X), because its own region has a cell on the edge: itself. So every cell on an edge keeps its letter, and only inner cells can change. A board with no inner cell, like the single cell of example 2, always comes back unchanged.

2. Hint 2: Ask a smaller question

   Picture a column of three O cells that starts on the top edge and runs down into a large board. The lowest of the three is not on any edge. Does it become X? What decides the fate of an inner O: where it is, or what it is joined to?

3. Hint 3: Name the pattern

   A region is a connected component of O cells: a group in which you can walk from any cell to any other. Regions with a cell on an edge are safe, so start from the edge O cells and spread through neighbors, marking every O you reach. Unmarked O cells are surrounded. This is the pattern grid connected components. Read the lesson on grid connected components.

4. Hint 4: State the invariant

   A cell gets the mark only if it is an O on an edge, or an O next to a marked cell. So every marked cell is joined to an edge through O cells, and once the spreading stops, every O that is joined to an edge has the mark.

5. Hint 5: Sketch the pseudocode

   mark(cell): if it is inside the board and holds O, write a third character there and add the cell to a waiting list. Mark every edge cell. Until the list is empty: take a cell off and mark its four neighbors. Then rewrite the board: the third character becomes O, everything else X. Return the board.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Mark all border-connected O cells as safe, then capture every unmarked O and restore the safe cells.

The slow way

For every O, walk through its region and look for a cell on an edge; if the walk finds none, that O is surrounded. Collect those cells and change them at the end. It is correct, but a region is walked again from each of its cells: a board that is one big region costs about cells × cells steps.

The insight

An O survives for one reason only: it is joined, through O cells, to an O on an edge. So do not test regions one by one. Start from the edge O cells and spread through their neighbors. Everything you reach is safe, and every O you did not reach is surrounded.

Step by step

1. Measure the board and start an empty queue of safe cells. The size tells where the edges are. The queue is a waiting line, first in, first out, for safe cells whose own neighbors have not been looked at yet.
2. To mark a cell: only an O inside the board is tagged and queued. Tagging replaces the O by a third character, #, so a safe cell can be told apart from an X and from an O not reached yet. A tagged cell is no longer O, so it cannot be queued twice.
3. Mark the O cells on the four edges: they can never be captured. Captured means changed to X. A region with a cell on an edge is not surrounded, and an edge O is such a cell of its own region. These cells are the starting points of the spreading.
4. Take each queued cell in turn and mark its four neighbors. An O beside a safe cell belongs to the same region, so it is safe too. Marking it queues it, and so the spreading goes on until the whole region is tagged.
5. Rewrite the board: a tagged cell is O again, every other cell is X. After the spreading, an O without a tag is not joined to any edge, so it is surrounded and becomes X. The tag was only a note for the method and must not stay in the answer.
6. Return the board. The checker reads the value the function returns, so the changed board has to be handed back, not only changed in place.

The same numbered steps are the comments in each solution.

function solve(board) {
  // 1. Measure the board and start an empty queue of safe cells
  // A board with no rows has no first row: ?. and ?? then give 0 columns.
  const rows = board.length,
    cols = board[0]?.length ?? 0,
    q = [];
  // 2. To mark a cell: only an O inside the board is tagged and queued
  function mark(r, c) {
    // Outside the board, board[r]?.[c] is undefined, which is not "O".
    if (board[r]?.[c] === "O") {
      board[r][c] = "#";
      q.push([r, c]);
    }
  }
  // 3. Mark the O cells on the four edges: they can never be captured
  for (let r = 0; r < rows; r++) {
    mark(r, 0);
    mark(r, cols - 1);
  }
  for (let c = 0; c < cols; c++) {
    mark(0, c);
    mark(rows - 1, c);
  }
  // 4. Take each queued cell in turn and mark its four neighbors
  // i walks along the queue, so no cell has to be removed from its front.
  for (let i = 0; i < q.length; i++) {
    const [r, c] = q[i];
    mark(r + 1, c);
    mark(r - 1, c);
    mark(r, c + 1);
    mark(r, c - 1);
  }
  // 5. Rewrite the board: a tagged cell is O again, every other cell is X
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      board[r][c] = board[r][c] === "#" ? "O" : "X";
  // 6. Return the board
  return board;
}

function solve(board: string[][]): string[][] {
  // 1. Measure the board and start an empty queue of safe cells
  // A board with no rows has no first row: ?. and ?? then give 0 columns.
  const rows = board.length,
    cols = board[0]?.length ?? 0,
    q: number[][] = [];
  // 2. To mark a cell: only an O inside the board is tagged and queued
  function mark(r: number, c: number): void {
    // Outside the board, board[r]?.[c] is undefined, which is not "O".
    if (board[r]?.[c] === "O") {
      board[r][c] = "#";
      q.push([r, c]);
    }
  }
  // 3. Mark the O cells on the four edges: they can never be captured
  for (let r = 0; r < rows; r++) {
    mark(r, 0);
    mark(r, cols - 1);
  }
  for (let c = 0; c < cols; c++) {
    mark(0, c);
    mark(rows - 1, c);
  }
  // 4. Take each queued cell in turn and mark its four neighbors
  // i walks along the queue, so no cell has to be removed from its front.
  for (let i = 0; i < q.length; i++) {
    const [r, c] = q[i];
    mark(r + 1, c);
    mark(r - 1, c);
    mark(r, c + 1);
    mark(r, c - 1);
  }
  // 5. Rewrite the board: a tagged cell is O again, every other cell is X
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      board[r][c] = board[r][c] === "#" ? "O" : "X";
  // 6. Return the board
  return board;
}

from collections import deque


def solve(board):
    # 1. Measure the board and start an empty queue of safe cells
    rows = len(board)
    # A board with no rows has no first row to measure, so it gets 0 columns.
    cols = len(board[0]) if board else 0
    # A deque is a list that is fast at both ends: append adds at the back,
    # popleft takes from the front.
    queue = deque()

    # 2. To mark a cell: only an O inside the board is tagged and queued
    def mark(r, c):
        if 0 <= r < rows and 0 <= c < cols and board[r][c] == "O":
            board[r][c] = "#"
            queue.append((r, c))

    # 3. Mark the O cells on the four edges: they can never be captured
    for r in range(rows):
        mark(r, 0)
        mark(r, cols - 1)
    for c in range(cols):
        mark(0, c)
        mark(rows - 1, c)
    # 4. Take each queued cell in turn and mark its four neighbors
    while queue:
        r, c = queue.popleft()
        mark(r + 1, c)
        mark(r - 1, c)
        mark(r, c + 1)
        mark(r, c - 1)
    # 5. Rewrite the board: a tagged cell is O again, every other cell is X
    for r in range(rows):
        for c in range(cols):
            board[r][c] = "O" if board[r][c] == "#" else "X"
    # 6. Return the board
    return board

Example 1, traced

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

Why it works

The spreading tags exactly the O cells that are joined to an edge through O cells: it starts at every edge O, and it moves only from a tagged cell to a neighboring O, as far as it can go. An untagged O therefore belongs to a region with no cell on an edge, which is what surrounded means. Only those cells become X.

Time and space

Time O(rows · cols), extra space O(rows · cols). The board has rows · cols cells. A cell is tagged at most once, so it is queued and spreads at most once; the final rewrite visits each cell once: O(rows · cols) time. The queue never holds more cells than the board has: O(rows · cols) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• An inner O is not always surrounded. In the board with rows XOX, XOX and XXX the middle O is joined to the O on the top edge and must stay. Without spreading from the edge cells it becomes X.
• In the final pass decide each cell once. Two separate tests, first tag to O and then O to X, turn a restored cell straight into X, and the whole board comes back as X.
• Cells that touch at a corner are not joined. If the spreading also follows diagonals, the first example keeps all three inner O cells, because one of them touches the safe O on the bottom edge at a corner.

Pattern

Grid connected components. Builds on Number of Islands and Pacific Atlantic Water Flow.

Keep going