LeetCode 130 · Graphs

Surrounded Regions, explained with a picture

Capturing surrounded stones on a Go board.

MediumGraphs
▶ Watch it step by step

The problem

On a board of X and O, capture every region of O that is completely surrounded by X (turn those O into X). An O region touching the border is never captured.

Input:  XXXX / XOOX / XXOX / XOXX
Output: XXXX / XXXX / XXXX / XOXX

Picture it

Picture a game of Go: white stones (O) fully surrounded by black (X) are captured. A white group is safe only if it touches the edge of the board. So we start from every white stone on the edge and mark its whole group as safe. Every white stone not marked safe gets captured.

How to recognise it

  • A grid of two kinds of cells, and the question is about groups of O cells joined side to side.
  • A group is judged by one property: does it touch the border? Border-connected groups are special, all others are not.
  • The change must be made in place, so you need a way to remember which cells are safe while you rewrite the rest.
  • A grid up to 200 × 200 means 40,000 cells, so one pass per region is fine but one pass per cell is not.

Start with brute force

Take each O cell, find its whole region with a fresh visited set, and check whether any cell of that region lies on the border. If none does, the region is surrounded, so mark its cells for capture.

def solve_brute(board):
    R, C = len(board), len(board[0])
    out = [row[:] for row in board]
    for r in range(R):
        for c in range(C):
            if board[r][c] == "O":
                seen, st = {(r, c)}, [(r, c)]
                touches = False
                while st:
                    a, b = st.pop()
                    if a in (0, R - 1) or b in (0, C - 1):
                        touches = True
                    for x, y in nbrs(board, a, b):
                        if board[x][y] == "O" and (x, y) not in seen:
                            seen.add((x, y)); st.append((x, y))
                if not touches:
                    out[r][c] = "X"
    return out

A region of k cells is searched k times, so a board full of O costs R·C searches of R·C cells: O((R·C)²) time, about 1.6 × 10^9 steps for 200 × 200. Space is O(R·C) for the copy and visited set.

From brute force to the idea

  1. Find the waste. The brute force asks the same question about every cell of a region and gets the same answer each time.
  2. Flip the question. Deciding who is surrounded is awkward. Deciding who is safe is easy: a cell is safe exactly when a chain of O cells links it to the border.
  3. Start from the border. The shown code puts every border cell in the queue. When it pops a cell that is an "O", it relabels it "S" (safe) and queues its neighbours. Border cells that are "X" are popped and ignored.
  4. Sweep once. After the queue is empty, every "O" left was never reached, so it is surrounded: turn it into "X". Every "S" goes back to "O".

The key idea: mark the survivors from the border inward, and everything else is captured.

The key idea

Flood fill from border O cells to mark the survivors, then flip the rest. O(rows × cols).

Python solution

def solve(board):
    R, C = len(board), len(board[0])
    q = deque()  # edge cells
    for r, c in all_cells(board):
        if r in (0, R-1) or c in (0, C-1):
            q.append((r, c))
    while q:  # edge-linked: safe
        r, c = q.popleft()
        if board[r][c] == "O":
            board[r][c] = "S"
            q.extend(nbrs(board, r, c))
    for r, c in all_cells(board):
        if board[r][c] == "O":
            board[r][c] = "X"     # captured
        if board[r][c] == "S":
            board[r][c] = "O"

def all_cells(g):
    return [(r, c) for r in range(len(g))
            for c in range(len(g[0]))]

def nbrs(g, r, c):  # in-grid neighbours
    R, C = len(g), len(g[0])
    for nr, nc in ((r+1, c), (r-1, c),
                   (r, c+1), (r, c-1)):
        if 0 <= nr < R and 0 <= nc < C:
            yield nr, nc

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO((R·C)²): one region search per O cellO(R·C): visited sets and an output copy
Border flood (shown code)O(R·C): every cell is expanded once; the queue takes at most about four pushes per cellO(R·C): the queue and the list from all_cells; the board is changed in place

Edge cases

  • A single cell ([["O"]] or [["X"]]): unchanged, since every cell is on the border.
  • Boards with 1 or 2 rows or columns: nothing is captured, because every cell is on the border.
  • An O in the middle of X (the 3 × 3 ring): becomes X.
  • An O region touching the border by one cell: the whole region survives.
  • Diagonal contact does not connect, so an O linked to the border only diagonally is captured.
  • The function returns None and changes the board itself. The same cell may sit in the queue several times; this is harmless because only an "O" is expanded. deque must be imported.

Common mistakes

  • Flooding from every interior O to see whether it escapes, which is the slow approach.
  • Capturing directly while searching, which flips border-connected regions that are found later.
  • Forgetting to restore the "S" cells to "O".
  • Seeding only the four corners or only the top row instead of the entire border.
  • Treating diagonals as connected.
Your turn: how many are captured?

Without changing the board, return how many O cells would be captured. Describe what changes, then write it if you like.

Compare with our answer

Keep the border-first idea, but record the safe cells in a set instead of rewriting the board, then count the O cells that are not in it.

def count_captured(board):
    R, C = len(board), len(board[0])
    safe, q = set(), deque()
    for r, c in all_cells(board):
        if (r in (0, R - 1) or c in (0, C - 1)) and board[r][c] == "O":
            safe.add((r, c)); q.append((r, c))
    while q:
        r, c = q.popleft()
        for nr, nc in nbrs(board, r, c):
            if board[nr][nc] == "O" and (nr, nc) not in safe:
                safe.add((nr, nc)); q.append((nr, nc))
    return sum(1 for r, c in all_cells(board)
               if board[r][c] == "O" and (r, c) not in safe)

Time O(R·C), space O(R·C).

A strong answer mentions: starting only from border O cells, a visited set instead of overwriting, and counting the O cells that were never reached.

Check what stuck

1. A grid marks land (1) and water (0). You must count the land cells that cannot reach the grid's edge by walking over land. Which approach fits best?

2. Why does the shown solution start its search from the border rather than from the surrounded regions?

3. A learner deletes the if board[r][c] == "S": board[r][c] = "O" lines from the final loop. Which input now returns a wrong board?

Score 60% or more and the lesson is marked complete.