What is the brute force approach and complexity for Surrounded Regions?

For each 'O', search its region; if no cell of it is on the edge, flip the whole region with time complexity O((m · n)²) and space complexity O(m · n).

What is the optimal approach and complexity for Surrounded Regions?

Mark every 'O' connected to the edge with '#', flip the other 'O's to 'X', then turn '#' back into 'O' with optimal time complexity O(m · n) and space complexity O(m · n).

How do you identify the pattern for Surrounded Regions?

Look for key signals in the prompt: "surrounded by 'X'" indicates An 'O' is captured only when no path of 'O's leads from it to the edge.; "connected 'O' cells form a region" indicates One search from a cell covers its whole region in one pass.; "on the edge of the board" indicates The safe starting points are the edge. Work from there instead of from every 'O'..

Surrounded Regions

Medium·LeetCode #130 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given a board of 'X' and 'O' letters. A region is a group of 'O' cells joined up, down, left or right. A region is surrounded when none of its 'O' cells is on the edge of the board. Turn every surrounded 'O' into 'X', in place. Regions that touch the edge stay as they are.

Input

board, an m × n grid of 'X' and 'O' characters. You change it in place.

Output

Nothing is returned. The board itself is changed.

Example 1

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

The three middle 'O's are joined to each other and never touch the edge, so they are captured. The 'O' in the bottom row is on the edge, so it stays.

Example 2

Input: board = [["X"]]

Output: [["X"]]

There is no 'O', so nothing changes.

Constraints

• 1 ≤ m, n ≤ 200, where m is the number of rows and n is the number of columns
• board[i][j] is 'X' or 'O'

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“surrounded by 'X'”

→ An 'O' is captured only when no path of 'O's leads from it to the edge.

“connected 'O' cells form a region”

→ One search from a cell covers its whole region in one pass.

“on the edge of the board”

→ The safe starting points are the edge. Work from there instead of from every 'O'.

Approach Complexity Ladder

Brute Force — search each region from every 'O', flip the enclosed onesO((m · n)²)O(m · n)

For each 'O', search its region; if no cell of it is on the edge, flip the whole region

Optimal — mark the edge-connected 'O's, flip the rest, restore the marksO(m · n)O(m · n)

Mark every 'O' connected to the edge with '#', flip the other 'O's to 'X', then turn '#' back into 'O'

Brute Force Intuition

For each 'O' that is still 'O', search its whole region with a fresh visited array. If none of its cells is on the edge, flip the whole region to 'X'. A region that touches the edge is searched again from each of its cells, so the same answer is found many times.

Recognition rule for this sub-pattern:

Start a DFS/BFS from each unvisited cell; everything it reaches is one component.

Remember this · Graph BFS / DFS

Trigger

Grid of cells, islands, regions, "minimum steps", transformations between states, connected components.

Think

What is a node, what is an edge, and do I need the shortest path or just reachability?

Key question

How do I mark visited so I never process a node twice?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Food Delivery System (Zomato / DoorDash)

Geospatial indexing and shortest dispatch routing for delivery partners.

Explore Track

C++ Internals

Virtual Method Table (vtable) & Dynamic Dispatch

Polymorphic graph nodes and state machine execution overhead.

Explore Track

Number of Enclaves Pacific Atlantic Water Flow