Surrounded Regions

Table of Contents +

Surrounded Regions tricks a lot of people. The obvious plan is to hunt for trapped regions one by one. The clever plan does the opposite. You find the cells that are safe first, then flip everything else. That backwards move is what makes this question click.

🎯 The Problem

You flip every trapped group of O cells into X, but leave the ones that escape.

  • The grid holds X and O. Think of O as open cells and X as walls.
  • A region of O cells is captured if it is fully surrounded by X and never touches the border.
  • Flip every captured O into an X.
  • An O that touches the border, or connects to one that does, is safe. Leave it alone.

Here is a small grid.

Input grid:
  X  X  X  X
  X  O  O  X
  X  X  O  X
  X  O  X  X


After flipping captured regions:
  X  X  X  X
  X  X  X  X
  X  X  X  X
  X  O  X  X


Explanation: the middle O group is fully boxed in by X, so it is
captured and flipped. The O at [3,1] sits on the border, so it stays.

The O at row 3 column 1 sits on the bottom edge. The bottom edge is the border. So that cell is safe and stays an O. The middle group is boxed in, so it gets captured.

Here is the grid. The middle blob is trapped. The border cell escapes.

O at 3,1 on the border

safe, stays O

O at 1,1

O at 1,2

O at 2,2

surrounded, becomes X

🐢 Approach 1: Check Each Region (Brute Force)

We look at each group of O cells and ask if it is trapped.

The idea:

  • Flood each region of O cells and watch every cell in it.
  • If any cell sits on the border, the region is safe.
  • If none do, flip the whole region to X.

How it works:

  • Hold all the cells of a region in memory while you decide.
  • Then go back and flip the trapped ones.

Why it is weak:

  • The “remember the region, then maybe undo” logic is easy to get wrong.
  • Off by one mistakes creep in.
  • You repeat the same bookkeeping for every region.

Here is the region-check code:

surrounded_regions_region_check.py
def solve(board):
    rows, cols = len(board), len(board[0])
    seen = set()
    def collect(r, c, group):
        if r < 0 or c < 0 or r == rows or c == cols: return False
        if board[r][c] != "O" or (r, c) in seen: return True
        seen.add((r, c)); group.append((r, c))
        return all(collect(nr, nc, group) for nr, nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)))
    for r in range(rows):
        for c in range(cols):
            group = []
            if board[r][c] == "O" and (r, c) not in seen and collect(r, c, group):
                for x, y in group: board[x][y] = "X"

⚡ Approach 2: Flood From the Border (Best)

The idea in one line: do not hunt for trapped regions, find the safe ones first and flip the rest.

The idea:

  • A region is safe only if it touches the border. So start the flood from the border itself.
  • Walk along the four edges. Every O you find on an edge starts a flood fill.
  • Mark each connected O with a temporary letter, say S for safe.

How it works:

  • After the border flood, any O still showing is trapped, because the flood never reached it.
  • Any S is a safe cell that touched the border.
  • Make one final pass. Turn every leftover O into X. Turn every S back into O.

DFS or BFS, your choice:

  • DFS, depth first search, uses recursion to dive along one path.
  • BFS, breadth first search, uses a queue to spread in rings.
  • Both reach the same border connected cells. What matters is the direction. Start from the safe edge, not the trapped middle.

Here is the border flood marking safe cells, then the final flip.

flood fill

border O cell

mark as S = safe

final pass: S back to O

O never reached

final pass: O to X

Steps to Solve

  1. Go along the top row, bottom row, left column, and right column.
  2. For each O found on those edges, run a flood fill. Mark every connected O as a temporary safe letter S.
  3. After the border flood is done, scan the whole grid one more time.
  4. If a cell is still O, it was never reached from the border, so it is captured. Turn it into X.
  5. If a cell is S, it was safe. Turn it back into O.

This Python version floods from the border with recursive DFS and marks safe cells with “S”.

surrounded_regions.py
grid = [
    ["X", "X", "X", "X"],
    ["X", "O", "O", "X"],
    ["X", "X", "O", "X"],
    ["X", "O", "X", "X"],
]
R, C = len(grid), len(grid[0])




def mark(r, c):
    if r < 0 or r >= R or c < 0 or c >= C:   # off the grid
        return
    if grid[r][c] != "O":                    # wall or already marked
        return
    grid[r][c] = "S"                         # mark as safe
    mark(r + 1, c)
    mark(r - 1, c)
    mark(r, c + 1)
    mark(r, c - 1)




for i in range(R):
    mark(i, 0)         # left column
    mark(i, C - 1)     # right column
for j in range(C):
    mark(0, j)         # top row
    mark(R - 1, j)     # bottom row


for i in range(R):
    for j in range(C):
        if grid[i][j] == "O":      # never reached, captured
            grid[i][j] = "X"
        elif grid[i][j] == "S":    # safe, put it back
            grid[i][j] = "O"


for row in grid:
    print(" ".join(row))

The output of the above code will be:

X X X X
X X X X
X X X X
X O X X

Now let us read the Python version line by line. The mark function does the border flood. It marks every O that connects to the border as safe.

The first check if r < 0 or r >= R or c < 0 or c >= C: return stops us when the cell is off the grid. The second check if grid[r][c] != "O": return stops us on a wall, and it also stops us on a cell we already marked S. So this one check handles walls and stops repeat visits at the same time.

The line grid[r][c] = "S" is the heart of it. We turn this border connected O into S, which stands for safe. Then the four recursive calls flood into the neighbors. So one call from an edge cell spreads the safe mark across the whole connected region that touches the edge.

The two loops over i and j start the flood from the edges only. The left and right columns, then the top and bottom rows. We never start from the middle. That is the whole idea.

The final double loop does the flip. A cell still showing O was never reached, so it is captured and becomes X. A cell showing S was safe, so we restore it to O. After this pass the grid holds the final answer.

⏱️ Time and Space Complexity

The border flood visits each cell a small fixed number of times. The final flip pass visits each cell once. So the total time is O(n), where n is the number of cells. The space is O(n) in the worst case, because the recursion can go as deep as the number of cells in one large region, or the BFS queue can hold many cells.

Approach Time Complexity Space Complexity
Check each region (brute force) O(n) O(n)
Flood from the border O(n) O(n)

Tip

The flip in thinking is the lesson here. Do not search for what you want to capture. Search for what is safe, mark it, then capture everything else. This pattern shows up in many grid problems.

🧩 Key Takeaways

  • ✅ A region is safe only if it touches the border of the grid.
  • ✅ Flood from the border to mark every safe O, instead of hunting for trapped ones.
  • ✅ Use a temporary letter like S so you can tell safe cells from captured ones.
  • ✅ After the flood, leftover O cells are captured, and S cells go back to O.
  • ✅ The whole thing runs in O(n) time, where n is the number of cells.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    When is a region of O cells safe from capture?

    Why: Any O that touches the border, or connects to one that does, cannot be captured, so it is safe.

  2. 2

    Where do we start the flood fill in the optimal approach?

    Why: We flood only from border O cells so we mark exactly the safe, border connected regions.

  3. 3

    After the border flood, what does a remaining plain O cell mean?

    Why: If the border flood never reached it, the cell is trapped, so we flip it to X.

  4. 4

    Why use a temporary letter like S during the flood?

    Why: Marking safe cells with S lets the final pass restore them to O while flipping the rest to X.

Score: 0 / 4

🚀 What’s Next?

Previous Max Area of Island Next Rotting Oranges