DSA sheet · Graphs · Grid traversal · start from the border

Surrounded Regions

This problem looks like "find every closed group of O's and paint it X". The teacher shows that checking each group from the inside is the hard way. The easy way is to turn the question around: start from the border and walk inwards. Any O that touches the border can never be captured, and neither can any O joined to it. Mark those as "safe" with one BFS per border O, then flip everything else. She first keeps a separate visited grid, then removes it by writing a temporary # into the board itself. She codes it with BFS and asks us to also write the DFS version, which we do in Part C. The same "border first" trick comes back in the very next problem, Pacific Atlantic Water Flow.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Graph and grid basics this page needs
• Part A · Border BFS with a separate "safe" grid (the first idea)
• Part B · Border BFS, marking in place with # (the teacher's code)
• Part C · The same thing with DFS
• Part D · Revision page

Part 0 · Graph and grid basics this page needs

Nodes and edges

A graph is a set of points joined by lines. The points are nodes (also called vertices). The lines are edges. Two nodes joined by an edge are called neighbours.

(0)—(1)—(2)        (3)—(4)
 nodes: 0 1 2 3 4      edges: 0-1, 1-2, 3-4

Directed, undirected, weighted

Three ways a graph can be given, and building an adjacency list

n = 5
edges = [[0, 1], [1, 2], [3, 4]]
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)        # undirected: add both ways
print(adj)                  # [[1], [0, 2], [1], [4], [3]]

In this problem we never build an adjacency list: the grid itself tells us the neighbours, as shown below.

Visited, and connected components

In an undirected graph, 0 lists 1 as a neighbour and 1 lists 0 back. A walk that does not remember where it has been goes 0 → 1 → 0 → 1… forever. So every traversal keeps a visited mark: mark a node the moment you reach it, and never enter a marked node again. A connected component is a group of nodes that can all reach each other, with nothing outside the group reachable. In this problem, a region is exactly a connected component of O cells.

BFS and DFS

from collections import deque

def bfs(start, adj, visited):
    q = deque([start])
    visited[start] = True            # mark when you ADD to the queue
    while q:
        u = q.popleft()
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)

def dfs(u, adj, visited):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v, adj, visited)

adj = [[1], [0, 2], [1], [4], [3]]
seen = [False] * 5
bfs(0, adj, seen)
print(seen)                          # [True, True, True, False, False]
dfs(3, adj, seen)
print(seen)                          # [True, True, True, True, True]

A grid is a graph

Each cell (r, c) is a node. Its neighbours are the 4 cells up, down, left and right (no diagonals in this problem). We keep the 4 moves in a small list of (dr, dc) pairs: how much the row and the column change.

            (r-1, c)
               ↑  (-1, 0)
(r, c-1) ← (r, c) → (r, c+1)
  (0,-1)       ↓     (0, +1)
            (r+1, c)
               (+1, 0)

Before touching a neighbour (nr, nc), do the bounds check 0 <= nr < rows and 0 <= nc < cols, or a border cell will look outside the board (in Python, a −1 index silently wraps to the last row, which is an even sneakier bug than a crash). And instead of a separate visited grid we can often mark visited in place, by overwriting the cell with a value that no longer passes the "should I go here?" test. That is exactly the trick of Part B.

grid = ["XOX",
        "OOX"]
rows, cols = len(grid), len(grid[0])
r, c = 1, 1
for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):   # up, down, left, right
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        print((nr, nc), grid[nr][nc])
# prints (0, 1) O, then (1, 0) O, then (1, 2) X  (down is outside)

Part A · Border BFS with a separate "safe" grid

LeetCode 130 · Surrounded Regions

1The question in simple words

You get a board of 'X' and 'O' letters. O cells that touch each other up/down/left/right form a region. A region is surrounded when none of its cells sits on the edge of the board, so it is fully closed in by X's. Capture every surrounded region by turning all its O's into X's. Change the board in place; return nothing.

     c0 c1 c2 c3
r0   X  X  X  X
r1   X  O  O  X
r2   X  X  O  X
r3   X  O  X  X

     c0 c1 c2 c3
r0   X  X  X  X
r1   X  X  X  X
r2   X  X  X  X
r3   X  O  X  X   ← stays O

The three O's at (1,1), (1,2), (2,2) are one region, and it is closed in on every side, so they all become X. The O at (3,1) is on the bottom edge, so it stays.

2What the constraints tell us

• 1 ≤ m, n ≤ 200 → the board is never empty, so board[0] is always safe to read. At most 200 × 200 = 40,000 cells.
• An O(m·n) solution is about 40,000 steps, which is instant. But "for every cell, run a full search" is about (m·n)² = 1.6 × 10⁹ steps, which is far beyond the rough 10⁸ limit and would get TLE. So we want each cell handled a constant number of times.
• Every cell is 'X' or 'O'. That means any third character, like '#', is free for us to use as a temporary mark (Part B).

(The teacher doesn't read the constraints aloud in this video; the reasoning above is ours, using her usual checklist: base case? fast enough?)

3Intuition: think about who can NOT be captured

Picture the board as a lake. X is land, O is water. Water on the edge of the board leaks out into the sea. Any water connected to that leaking water also drains away. Only water in a closed pond stays put, and a closed pond is exactly a surrounded region.

So instead of asking, for every region, "are you closed?", ask the easy opposite question: "which O's are connected to the border?" Those are safe. Every other O is captured.

4Building the logic from the teacher's examples

Step 1: what does "surrounded" really need?

Look at the O at (1,1) in Example 1. Above it is X, left of it is X, below it is X, but to its right is another O, not an X. Is it still surrounded? Yes. The teacher's point: one cell doesn't need X on all four of its own sides. If a side has an O, that O belongs to the same region, and the region as a whole just has to be fenced. The O at (1,2) supplies the missing X on the right, the O at (2,2) supplies the X further down, and so on. Every path out of the region eventually hits an X.

     X  X  X  X
     X [O][O] X      [ ] = the region
     X  X [O] X      every step outward from a [ ] cell
     X  O  X  X      lands on X or on another [ ] cell

Step 2: what breaks it? Reaching the edge

Now she changes the picture: suppose there is no row of X under the region, so the bottom O of the region sits on the last row. When you try to step down from it, you fall off the board instead of hitting an X. There is no fence on that side, so the region is not surrounded. It doesn't matter that every other side is fenced.

X  X  O  X     ← edge O
X  O  O  X
X  X  O  X
X  O  X  X

X  X  O  X
X  O  O  X     all 4 O's are joined
X  X  O  X     to the edge O, so
X  O  X  X     all stay O

One O on the border spoils its whole region: every O joined to it, directly or through other O's, can step its way to that border cell and out. So the rule is about the border:

Step 3: the special case that makes it click

The teacher asks: what if every border cell is X? Then no O anywhere can reach the edge, so every O inside is captured. Two loops that flip all O's to X would finish the job. The border is the only thing that can save an O, which is why we only need to start our searches from the border.

Step 4: remembering the safe cells

Walk around the 4 borders. Whenever a border cell is O, it's safe, and so is every O connected to it. Finding "every O connected to this cell" is a plain BFS (or DFS) on the grid, only stepping onto cells that are O and inside the board. Her first idea is to remember the safe cells in a separate grid safe of the same size, all False at the start, set to True for each safe O.

Then a final pass over every cell: O and not safe → turn into X. O and safe → leave it.

5Approach steps

1. Make safe, an m × n grid of False.
2. Walk the first and last column, and the first and last row.
3. For every border cell that is O and not safe: BFS from it, marking every reachable O as safe.
4. Walk every cell: if it's O and not safe, change it to X.

6Code (Python)

from collections import deque

class Solution:
    def solve(self, board):
        n, m = len(board), len(board[0])
        safe = [[False] * m for _ in range(n)]

        def bfs(r, c):
            q = deque([(r, c)])
            safe[r][c] = True
            while q:
                r, c = q.popleft()
                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < n and 0 <= nc < m
                            and board[nr][nc] == 'O' and not safe[nr][nc]):
                        safe[nr][nc] = True
                        q.append((nr, nc))

        for i in range(n):                       # first and last column
            for j in (0, m - 1):
                if board[i][j] == 'O' and not safe[i][j]:
                    bfs(i, j)
        for j in range(m):                       # first and last row
            for i in (0, n - 1):
                if board[i][j] == 'O' and not safe[i][j]:
                    bfs(i, j)

        for i in range(n):
            for j in range(m):
                if board[i][j] == 'O' and not safe[i][j]:
                    board[i][j] = 'X'            # trapped -> captured

7Code line by line

8Dry run

The dry run is identical to Part B's, with "safe = True" in place of "write #". We do it once, in Part B, where it matters most.

9Complexity & remember

• Time O(m·n): border loops are O(2m + 2n); each O becomes safe once, so all BFS calls together touch each cell a constant number of times; the final pass is m·n.
• Space O(m·n): the safe grid, plus the queue.

Part B · Border BFS, marking in place with #

1The question

Same question, same idea. The only goal now is to drop the extra safe grid.

2What the constraints tell us

Cells are only ever 'X' or 'O', so a third symbol is free to carry extra information. That is the whole trick.

3Intuition: write the "safe" flag into the board itself

The teacher's line of thought: in the final pass we flip every cell that reads as O. We don't want the safe O's to be flipped, so let's make them temporarily not read as O. Paint them with a third symbol, say # (not X, not O). The final pass then has three cases:

4Building the logic: why # also acts as "visited"

The BFS only steps onto cells that are O. The moment we paint a cell #, it stops being O, so no later step can walk into it again. The paint does double duty: it is the safe flag and the visited mark. That's why this version needs no visited grid at all.

Her walk-through around one border O: from it, look up → X, don't go. Look left → X, don't go. Look down → off the board, don't go. Look at the cell we came from → it's already #, not O, so don't go. Only real O neighbours are painted and queued.

5Approach steps

1. For each cell in the first column, last column, first row and last row: if it's O, BFS from it.
2. The BFS paints the start cell #, then repeatedly pops a cell and paints + queues every in-bounds O neighbour.
3. Walk the whole board: O → X (captured), # → O (restored).

6Code (Python)

from collections import deque

class Solution:
    def solve(self, board):
        n, m = len(board), len(board[0])

        def bfs(r, c):
            q = deque([(r, c)])
            board[r][c] = '#'                    # safe, and visited
            while q:
                r, c = q.popleft()
                for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < m and board[nr][nc] == 'O':
                        board[nr][nc] = '#'
                        q.append((nr, nc))

        for i in range(n):
            if board[i][0] == 'O':               # first column
                bfs(i, 0)
            if board[i][m - 1] == 'O':           # last column
                bfs(i, m - 1)
        for j in range(m):
            if board[0][j] == 'O':               # first row
                bfs(0, j)
            if board[n - 1][j] == 'O':           # last row
                bfs(n - 1, j)

        for i in range(n):
            for j in range(m):
                if board[i][j] == 'O':
                    board[i][j] = 'X'            # trapped: capture
                elif board[i][j] == '#':
                    board[i][j] = 'O'            # was safe: restore

7Code line by line

8Dry run

A slightly bigger board, so we see two separate border searches and one captured region. Loop order is the code's: column checks for each row i, then row checks for each column j.

     c0 c1 c2 c3 c4
r0   X  X  X  X  X
r1   X  O  O  X  X      inner region {(1,1),(1,2),(2,2)}
r2   X  X  O  X  O      ← (2,4) is a border O
r3   X  O  X  O  O      ← (3,4) border O, (3,3) joined to it
r4   X  O  X  X  X      ← (4,1) border O, (3,1) joined to it

X  X  X  X  X
X  O  O  X  X
X  X  O  X  #
X  #  X  #  #
X  #  X  X  X

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

The inner region was never painted, because no border search could reach it, so the final pass captured it ✓. The two border-connected groups came back as O ✓.

9Complexity & remember

• Time O(m·n). The teacher's argument: the border loops are O(2n + 2m), which is small. One BFS can, in the worst case, run over the whole board (imagine all O's). But then every O is now #, so all the other border checks find # and start nothing. Each cell is painted at most once across all searches, so together they cost m·n, not m·n per border cell. Add the final m·n pass: still O(m·n).
• Space O(m·n) in the worst case, for the queue (an all-O board can put many cells in it). No visited grid any more.

Part C · The same thing with DFS

The teacher points out that this problem is only a traversal: we just need to reach every O connected to a border O. BFS and DFS reach exactly the same cells, so DFS works equally well. She asks us to submit the DFS version ourselves. Steps ①–③ are the same as Part B.

4What changes

• No queue. The function paints its cell and calls itself on each O neighbour. The call stack remembers where to come back to.
• The check moves to the start of the function: "if this cell is off the board, or not O, return". Then the caller can blindly call on all 4 neighbours.
• The border loops and the final pass are unchanged.

5Approach steps

1. dfs(r, c): if out of bounds or not O → return.
2. Paint #, then call dfs on up, down, left, right.
3. Call dfs on every border cell; then do the same final pass as Part B.

6Code (Python)

import sys

class Solution:
    def solve(self, board):
        sys.setrecursionlimit(100000)
        n, m = len(board), len(board[0])

        def dfs(r, c):
            if r < 0 or r >= n or c < 0 or c >= m or board[r][c] != 'O':
                return
            board[r][c] = '#'
            dfs(r - 1, c)
            dfs(r + 1, c)
            dfs(r, c - 1)
            dfs(r, c + 1)

        for i in range(n):
            dfs(i, 0)
            dfs(i, m - 1)
        for j in range(m):
            dfs(0, j)
            dfs(n - 1, j)

        for i in range(n):
            for j in range(m):
                if board[i][j] == 'O':
                    board[i][j] = 'X'
                elif board[i][j] == '#':
                    board[i][j] = 'O'

7Code line by line

8Dry run (call stack)

Same board as Part B. The first border O is (2,4):

1. dfs(2,4): O → paint #. Try up (1,4): X → returns at once. Try down:
2. dfs(3,4): O → paint #. Up (2,4) is # → returns. Down (4,4) X → returns. Left:
3. dfs(3,3): O → paint #. All 4 neighbours are X or # → each returns. dfs(3,3) is done.
4. Back in dfs(3,4): right is off the board → returns. dfs(3,4) done. Back in dfs(2,4): left (2,3) X, right off-board. Done.
5. Later, dfs(4,1) paints (4,1), goes up to dfs(3,1), which paints (3,1) and finds nothing more.
6. Final pass: same result as Part B ✓.

9Complexity & remember

• Time O(m·n): same reason, each O is painted once; calls on X/#/off-board cells return in O(1).
• Space O(m·n): the recursion stack in the worst case.

Part D · Revision page

b1 = [list("XXXX"), list("XOOX"), list("XXOX"), list("XOXX")]
Solution().solve(b1)
print(["".join(r) for r in b1])   # ['XXXX', 'XXXX', 'XXXX', 'XOXX']

b2 = [list("XXOX"), list("XOOX"), list("XXOX"), list("XOXX")]
Solution().solve(b2)
print(["".join(r) for r in b2])   # ['XXOX', 'XOOX', 'XXOX', 'XOXX']

b3 = [list("XXXXX"), list("XOOXX"), list("XXOXO"), list("XOXOO"), list("XOXXX")]
Solution().solve(b3)
print(["".join(r) for r in b3])   # ['XXXXX', 'XXXXX', 'XXXXO', 'XOXOO', 'XOXXX']

b4 = [["O"]]
Solution().solve(b4)
print(b4)                         # [['O']]

Based on this video: Surrounded Regions | Graph | Pattern-wise DSA sheet