LeetCode 130: Surrounded Regions DFS Solution

You’re staring at a grid of X’s and O’s in a high-stakes coding interview. LeetCode 130: Surrounded Regions. Flip the trapped O’s to X’s, but let the border-connected ones breathe free. Mess it up, and your dream gig slips away. Nail it — like with this visual DFS breakdown — and you’re the hero who thinks like an algorithm.

What a rush. This isn’t abstract theory. It’s the skill that lands you building self-driving car pathfinders or AI dungeon crawlers tomorrow.

Why LeetCode 130 Feels Like a Trap (Until It Doesn’t)

Look. Grids. X’s boxing in O’s. Sounds simple, right? Hunt surrounded regions, paint ‘em X. But here’s the gotcha — those sneaky O’s hugging the edge? Untouchable. They escape.

Brute force? Flood every O inward, check walls. Nightmare. Exponential time. No thanks.

And then — bam. The reverse genius. Mark border O’s first. DFS from edges, slap an ‘E’ on anything connected. Escaped. Now flip leftover O’s to X, restore E’s to O. Brilliant.

Use DFS to mark all ‘O’ cells connected to the border as ‘E’ (escaped). Then traverse the entire board: flip remaining ‘O’ cells to ‘X’ (captured) and restore ‘E’ cells back to ‘O’ (escaped).

That’s the core, straight from the solution playbook. Clean. O(m*n) time, same space. No recursion stack overflow scares if you’re careful (Python’s got limits, tweak to iterative if needed).

But wait. Why does this stump pros?

How Does the Border-First DFS Actually Flip the Script?

Start at the edges. Every border cell that’s ‘O’? DFS dive.

Visualize a 4x4 grid:

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

Border O at (1,1)? Nah. But say top row has one. Boom, dfs(0, col).

Inside dfs: Bounds check. Not ‘O’? Bail. Else ‘E’, recurse up, down, left, right.

It’s flood fill — but outward from safety. Like water rising from the ocean, claiming connected land before the inland lakes dry up.

def dfs(row, col):
    if (
        row < 0 or row >= len(board)
        or col < 0 or col >= len(board[0])
        or board[row][col] != "O"
    ):
        return
    board[row][col] = "E"
    dfs(row + 1, col)
    dfs(row - 1, col)
    dfs(row, col + 1)
    dfs(row, col - 1)

Hit all four borders: left column, right, top row, bottom. No overlaps — DFS marks as it goes.

Second pass: Scan whole board. Lone ‘O’? To ‘X’. ‘E’? Back to ‘O’. Done.

Try this on paper. That inner O pool? Doomed. Border chain? Spared. Mind blown yet?

Now, the code skeleton:

First, define dfs. Then loop borders, call dfs on ‘O’s. Finally, the flip/restore grid walk.

Energy here — it’s not rote. It’s a pattern you’ll reuse in image segmentation (AI cars spotting lanes), game maps (surround enemy bases), even robotics flood avoidance.

Is LeetCode 130 a Crystal Ball for AI Engineering Jobs?

Here’s my hot take, absent from the original trace: This mirrors Go’s territory capture. AlphaGo didn’t brute; it surrounded smartly, reverse-evaluating safe groups first. 2016 DeepMind stunned the world — now you’re training on the same logic.

AI’s platform shift? Undeniable. Tomorrow’s agents navigate state spaces like this grid. Master surrounded regions, and you’re prepped for reinforcement learning mazes, neural net graph traversals. Not hype — fact. FAANG interviews test exactly this: think inverted, visualize flows.

But — TraceLit? Solid tool. Steps every line visually. No black-box staring. (Though, prediction: AI will animate these traces live soon, predicting branches. Watch this space.)

Skeptical? Run it. Input:

[[‘X’,’X’,’X’,’X’], [‘X’,’O’,’O’,’X’], [‘X’,’X’,’O’,’X’], [‘X’,’O’,’X’,’X’]]

Output: Border O at bottom-left escapes? Wait, check connections. Inner O’s flip. Pure joy.

Deeper. Recursion depth? Worst case, whole board — m*n. Python defaults 1000; big grids? Iterative BFS swap. Pro move.

Space? Call stack mirrors visits. Fine.

Wander a sec: Ever flood-filled in Photoshop? Magic wand selects connected pixels. Same vibe — but code it, own it.

And for interviews? Verbalize: “I’ll mark escapes first, avoids rechecking borders later.” Interviewer nods. You’re in.

What If You’re New to DFS on Grids?

Don’t sweat. Grids as graphs: cells nodes, adjacents edges. Four directions — up down left right. Bounds? Your moat.

Practice: Islands count (LeetCode 200). Same DFS, count components.

Then this. Reverse it.

Analogy time — fireworks. Border sparks ignite chains first. Inner duds fizzle to X. Vivid? Good.

Pace picks up: Tools like TraceLit? Game-changer for visual learners. Step. Watch ‘E’s propagate. See the surround collapse.

One paragraph wonder: Irresistible.

Back. Corporate spin? LeetCode’s interview mill. But this problem? Timeless. Not fleeting trend.

Unique edge: In multiplayer games, this logic powers territory claims — think Risk, but automated. AI bots dominating online play? Built on this.

🧬 Related Insights

• Read more: Node.js Cuts Releases in Half: Sanity or Stagnation?
• Read more: Open Source Adoption Is Booming—But It’s Eating Teams Alive

Frequently Asked Questions

How do you solve LeetCode 130 Surrounded Regions?

Use DFS from borders to mark connected ‘O’s as ‘E’, then flip remaining ‘O’s to ‘X’ and ‘E’s back to ‘O’.

What is the time complexity for LeetCode 130?

O(m*n) — visit each cell at most once.

Why use DFS instead of BFS for Surrounded Regions?

Either works; DFS simpler recursively, same complexity. BFS if stack depth worries you.