Surrounded Regions — LeetCode 130 Python Solution
MediumDepth-First SearchBreadth-First SearchUnion FindArrayMatrix
- Problem
- #130
- Pattern
- Union-Find
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Python solution
Python
class Solution:
def solve(self, board: List[List[str]]) -> None:
def dfs(i: int, j: int):
if not (0 <= i < m and 0 <= j < n and board[i][j] == "O"):
return
board[i][j] = "."
for a, b in pairwise((-1, 0, 1, 0, -1)):
dfs(i + a, j + b)
m, n = len(board), len(board[0])
for i in range(m):
dfs(i, 0)
dfs(i, n - 1)
for j in range(n):
dfs(0, j)
dfs(m - 1, j)
for i in range(m):
for j in range(n):
if board[i][j] == ".":
board[i][j] = "O"
elif board[i][j] == "O":
board[i][j] = "X"Complexity
| Measure | Complexity |
|---|---|
| Time | O(m \times n) |
| Space | O(m \times n) auxiliary |
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 130. Surrounded Regions is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
On study lists
This problem is on NeetCode 150 and Top Interview 150.
Frequently asked questions
- How hard is LeetCode 130. Surrounded Regions?
- LeetCode 130. Surrounded Regions is rated Medium on LeetCode.
- What is the time complexity of LeetCode 130. Surrounded Regions?
- The Python solution on this page runs in O(m \times n).
- What is the space complexity of LeetCode 130. Surrounded Regions?
- The Python solution on this page uses O(m \times n) auxiliary space.
- What topics does LeetCode 130. Surrounded Regions cover?
- LeetCode 130. Surrounded Regions is tagged Depth-First Search, Breadth-First Search, Union Find, Array and Matrix on LeetCode.