Skip to content

Volume ITechnology

4.20.5 — Surrounded Regions ​

LeetCode 130 · Medium

The problem ​

In a grid of 'X' and 'O', flip every region of 'O' that is completely surrounded by 'X'. A region touching the border is not surrounded and survives.

X X X X          X X X X
X O O X    →     X X X X
X X O X          X X X X
X O X X          X O X X

The bottom-left O survives because it sits on the border.

The pattern ​

Checking each region for whether it touches the border needs a flood fill per region, and then a second pass to flip the losers. That works, but there is a cleaner way, and it is the same reversal as 4.20.4:

Do not look for the regions that are surrounded. Look for the ones that are not.

A picture to hold in mind ​

Imagine a large grassy field surrounded by a tall wall, but the wall has some holes in it. Inside the field, there are patches of grass ('O') and patches of mud ('X'). An army wants to burn all the grass that is completely trapped inside the mud. Instead of sending scouts to every single patch of grass to see if they can somehow navigate to the outer wall, the army simply starts from the outside. They walk through the holes in the wall, stepping only on grass, and plant a flag ('S' for safe) on every grassy patch they can reach. Once they've explored as far as they can from the borders, they stop. Then, they look at the whole map: any grass that doesn't have a flag must be completely surrounded by mud, so they burn it ('X'). Any grass with a flag is safe, so they just take the flag back ('O').

The brute force, and where it wastes work ​

A brute-force strategy might iterate over every single cell. If it finds an 'O', it launches a DFS to check if that specific connected component touches the border. During the DFS, it would need to store all visited 'O' cells in a temporary list. If the DFS hits a border, it leaves them alone; if it finishes without hitting a border, it iterates through the temporary list and flips them to 'X'. This is messy, requires significant bookkeeping per region, and causes massive redundant traversals if not managed perfectly (leading to O(N^2) time). The reverse thinking completely eliminates the need to track individual components.

A region survives exactly when it touches the border. So flood from every border 'O', mark everything reached as safe, and then flip every remaining 'O' — because anything not reached from the border is, by definition, enclosed.

Three passes, no per-region bookkeeping, and no need to know which region a cell belongs to.

The three passes ​

  1. Flood from the border, marking safe cells with a temporary character, say 'S'.
  2. Scan the whole grid. Every remaining 'O' was unreachable from the border → flip it to 'X'.
  3. Scan again, turning every 'S' back into 'O'.

The temporary marker is what lets one grid hold three states at once — enclosed, safe, and wall — without a second array.

The solution ​

python
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        if not board:  # (1)
            return
        rows, cols = len(board), len(board[0])

        def mark_safe(r: int, c: int):  # (2)
            if r < 0 or r >= rows or c < 0 or c >= cols:  # (3)
                return
            if board[r][c] != 'O':  # (4)
                return                       # wall, or already marked
            board[r][c] = 'S'  # (5)
            mark_safe(r + 1, c)  # (6)
            mark_safe(r - 1, c)
            mark_safe(r, c + 1)
            mark_safe(r, c - 1)

        # 1. flood from every border cell
        for r in range(rows):  # (7)
            mark_safe(r, 0)
            mark_safe(r, cols - 1)
        for c in range(cols):  # (8)
            mark_safe(0, c)
            mark_safe(rows - 1, c)

        # 2 and 3. flip the enclosed, restore the safe
        for r in range(rows):
            for c in range(cols):
                if board[r][c] == 'O':  # (9)
                    board[r][c] = 'X'        # never reached → enclosed
                elif board[r][c] == 'S':  # (10)
                    board[r][c] = 'O'        # restore
ts
function solve(board: string[][]): void {
  if (!board.length) return;  // (1)
  const rows = board.length, cols = board[0].length;

  function markSafe(r: number, c: number): void {  // (2)
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;  // (3)
    if (board[r][c] !== 'O') return;  // (4)
    board[r][c] = 'S';  // (5)
    markSafe(r + 1, c); markSafe(r - 1, c);  // (6)
    markSafe(r, c + 1); markSafe(r, c - 1);
  }

  for (let r = 0; r < rows; r++) { markSafe(r, 0); markSafe(r, cols - 1); }  // (7)
  for (let c = 0; c < cols; c++) { markSafe(0, c); markSafe(rows - 1, c); }  // (8)

  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === 'O') board[r][c] = 'X';  // (9)
      else if (board[r][c] === 'S') board[r][c] = 'O';  // (10)
    }
}

The flood only follows 'O'. An 'X' stops it, which is what makes a wall a wall.

Marking with 'S' doubles as the visited check. A cell already marked is no longer 'O', so the second condition rejects it and there is no infinite loop.

Passes 2 and 3 are folded into one loop, since flipping an 'O' and restoring an 'S' are independent — a cell is one or the other, never both.

Seeding the whole border, including corners twice, is harmless thanks to the visited check.

Line by line ​

(1) An empty board needs nothing.

(2) mark_safe(r, c) marks every 'O' connected to (r, c) as safe. We write 'S' for safe. An 'O' region is safe exactly when it touches the border, because then it is not surrounded.

(3) Off the board, so stop.

(4) An 'X', or an 'O' already marked safe, so stop.

(5) Mark this cell safe. Writing 'S' also stops the walk from coming back here.

(6) Spread to the four neighbours.

(7) Start from every cell in the left and right columns, and

(8) every cell in the top and bottom rows. Any 'O' connected to the border is now 'S'.

(9) Any 'O' still left was never reached from the border, so it is surrounded. Flip it to 'X'.

(10) Turn every safe 'S' back into 'O'.

Trace ​

Consider this 3x3 grid:

X X X
X O X
X O O
StepActionState of Grid
1mark_safe loops over Top/Left/Right bordersAll 'X', nothing changes.
2mark_safe loops over Bottom borderFinds 'O' at (2,1) and (2,2).
3DFS from (2,1). Marks it 'S'.[[X, X, X], [X, O, X], [X, S, O]]
4DFS recurses up to (1,1). Marks it 'S'.[[X, X, X], [X, S, X], [X, S, O]]
5DFS from (2,2). Marks it 'S'.[[X, X, X], [X, S, X], [X, S, S]]
6Pass 2 & 3. Loop over grid.
7(1,1) is 'S' -> 'O'[[X, X, X], [X, O, X], [X, S, S]]
8(2,1) is 'S' -> 'O'[[X, X, X], [X, O, X], [X, O, S]]
9(2,2) is 'S' -> 'O'[[X, X, X], [X, O, X], [X, O, O]]

(Note: In this specific example, no 'O' was trapped, so no 'X' flipping occurred. The edge 'O's saved the inner 'O').

Edge cases ​

  • A board of only 'X'. Nothing changes.
  • Every 'O' touches the border. Nothing is flipped.
  • A board one or two cells wide. Every cell is on the border, so nothing can be surrounded.

Complexity ​

O(rows \times cols) time — the flood touches each cell at most once, and the final scan is one more pass. To break it down: The first loops scan only the perimeter. The DFS only ever traverses cells that are currently 'O', immediately mutating them to 'S'. So across the entire algorithm, a cell is transformed at most twice ('O' \to 'S' \to 'O', or 'O' \to 'X'). Finally, the nested loops do exactly one pass over the grid. Total operations are strictly proportional to N.

O(rows \times cols) worst-case space for the recursion, when the whole grid is one connected 'O' region. In this scenario, the recursion call stack would grow to rows \times cols frames deep before winding down. BFS or an explicit stack removes that risk on large grids.

Where this goes next ​

The "find the survivors, then everything else loses" inversion is a recurring move:

  • Number of Closed Islands — same idea, counting instead of flipping.
  • Number of Enclaves — count the land cells that cannot walk off the grid.
  • Pacific Atlantic — search from the edges rather than from every cell. 4.20.4.
  • Garbage collection — a real system doing exactly this. A tracing collector marks everything reachable from the roots, then frees the rest. It never asks "is this object garbage"; it asks "is this object reachable", and the answer to the first is whatever is left. Chapter 3.4 covers it.

The general shape: when "surrounded", "unreachable" or "unused" is hard to test directly, mark what is definitely safe and take the complement.

What the interviewer will push on ​

"Why search from the border instead of from each region?" It avoids tracking which region a cell belongs to and whether that region ever touched an edge. One flood answers the question for the whole grid.

"Why a temporary marker?" The grid must hold three states during the middle of the algorithm — wall, safe, and not-yet-decided — and one character each is enough.

"What if the grid is huge?" BFS or an explicit stack, because the recursion can be rows × cols deep.

"Could you use union-find?" Yes. Union every 'O' with its 'O' neighbours. Add one extra node that stands for "the border", and union every border 'O' with it. Then a cell survives if it is in the same group as that extra node. It is more code and the same complexity. The extra-node trick is useful, because it turns "is this connected to anything in a set?" into one union-find question.

One thing to volunteer: mention garbage collection. It shows the inversion is a real technique rather than a puzzle-specific trick.

Next: 4.20.6 Rotting Oranges — the first BFS in this chapter where the answer is a number of steps.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet