130. Surrounded Regions

Surrounded Regions (LeetCode 130) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Connected Components / Island Counting subpattern.

• NeetCode 150 · #86 of 150 · Graphs
• NeetCode 250 · #152 of 250 · Graphs

How to solve Surrounded Regions

Surrounded Regions is a DFS Connected Components problem, part of Graph Traversal Patterns (DFS & BFS). Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.

Work towards the solution in these steps:

1. Consider treating the board as a graph where each cell is a node connected to its adjacent cells; graph traversal algorithms like DFS or BFS can help identify connected regions.
2. Focus on the 'O' cells that are on the edges or connected to the edges; these cells cannot be captured as they are not fully surrounded by 'X's.
3. Use DFS or BFS starting from the edge 'O's to mark all 'O's connected to the edge, distinguishing them from the surrounded regions.

The reference solution runs in O(m * n) time and O(m * n) space.

The Surrounded Regions solution and editorial walks through the full approach with reference code.

Problem statement

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

- Connect: A cell is connected to adjacent cells horizontally or vertically.

- Region: To form a region connect every 'O' cell.

- Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

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"]]

Explanation:

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2:

Input: board = [["X"]]

Output: [["X"]]

Constraints:

- m == board.length

- n == board[i].length

- 1 <= m, n <= 200

- board[i][j] is 'X' or 'O'.

Topics and companies

Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix.

Reported in interviews at Amazon, Facebook, Google, Uber.

How to practise Surrounded Regions on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(m * n) space.

Open Surrounded Regions in the code editor, or read the Surrounded Regions editorial for a worked solution with its approach and complexity analysis.

Where Surrounded Regions sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Graph DFS - Connected Components / Island Counting subpattern
• The full DSA patterns sheet

Problems related to Surrounded Regions

Other problems that use the same Graph DFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:

• Count Sub Islands — Medium, same subpattern
• Detonate the Maximum Bombs — Medium, same subpattern
• Evaluate Division — Medium, same subpattern
• Flood Fill — Easy, same subpattern
• Island Perimeter — Easy, same subpattern
• Keys and Rooms — Medium, same subpattern

Surrounded Regions FAQ