DSA Tracker

Visualize

Surrounded Regions

Search inward from the border, then capture what is left

time O(rows * cols)space O(rows * cols) recursion stack

Searching for enclosed regions directly is awkward: you cannot tell a region is surrounded until you have seen all of it, so a half-finished walk proves nothing. Inverting the question removes that problem entirely. A region survives exactly when it touches an edge, and that is checkable from the outside in — start a search at every border O, mark everything it reaches, and stop. One pass over the border decides every cell on the board: whatever the search never touched is enclosed, by definition rather than by re-checking. The third marker value (#) exists only to keep 'survived' distinct from 'was always X' until the final sweep.

Details

Animated on: board = [[X,X,X,X,X],[X,O,O,X,O],[X,X,O,X,O],[X,O,X,X,O]] — flip every O region that is fully enclosed by X.

Problem:Surrounded RegionsMedium

Search inward from the border, then capture what is left

step 1 / 13

board

A region of O's is captured only if NONE of its cells touches an edge. So instead of hunting for enclosed regions, find the few that escape: every O reachable from the border survives, and everything else is surrounded by definition.

Pseudocode
1FUNCTION solve(board):
2  FOR each border cell (r, c):
3    IF board[r][c] = 'O': mark(r, c)
4  FOR each cell (r, c):
5    IF board[r][c] = 'O': board[r][c] <- 'X'
6    IF board[r][c] = '#': board[r][c] <- 'O'
7  RETURN board
8FUNCTION mark(r, c):
9  IF (r, c) outside board OR board[r][c] != 'O': RETURN
10  board[r][c] <- '#'
11  mark(r-1, c)
12  mark(r+1, c)
13  mark(r, c-1)
14  mark(r, c+1)

← / → step · space play · Home restart

Every step in words

Show all 13 steps
  1. A region of O's is captured only if NONE of its cells touches an edge. So instead of hunting for enclosed regions, find the few that escape: every O reachable from the border survives, and everything else is surrounded by definition.
  2. Only the 14 highlighted border cells can be entry points, and just 4 of them hold an O — (1,4), (2,4), (3,1), (3,4). Those are the only places a surviving region can start.
  3. (1,4) is an O sitting on the border, so it can never be surrounded. Park it as # — a third value, so the sweep later can tell "survived" from "was already X".
  4. (2,4) is an O touching a cell already marked #, so it escapes through that same opening. Mark it and keep walking; 2 cells are safe so far.
  5. (3,4) is an O touching a cell already marked #, so it escapes through that same opening. Mark it and keep walking; 3 cells are safe so far.
  6. The walk from (1,4) unwinds: every neighbour of those 3 cells is an X or off the board, so this region is closed at (1,4), (2,4), (3,4).
  7. (3,1) is an O sitting on the border, so it can never be surrounded. Park it as # — a third value, so the sweep later can tell "survived" from "was already X".
  8. The walk from (3,1) unwinds: every neighbour of that single cell is an X or off the board, so this region is closed at (3,1).
  9. Border scan done: 4 cells are marked #. Every O still on the board was never reached from an edge, so all 3 of them are surrounded — no second search is needed to prove it.
  10. (1,1) was never reached, so flip it to X. 2 trapped cells left.
  11. (1,2) was never reached, so flip it to X. 1 trapped cell left.
  12. (2,2) was never reached, so flip it to X. 0 trapped cells left.
  13. Restore the 4 # cells back to O and the board is final: the 3 enclosed cells were captured, the border-connected ones survived untouched.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Surrounded Regions in the editorAll Graph problemsBack to roadmap