MediumNo. 0959
Regions Cut By Slashes — LeetCode 959 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Array, Hash Table, Matrix
- Reading time
- 6 min
- Source
- leetcode.com
The problem
An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a '/', '\', or blank space ' '. These characters divide the square into contiguous regions.
Example
- Input
- grid = [" /","/ "]
- Output
- 2
Python solution
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
def union(a, b):
pa, pb = find(a), find(b)
if pa != pb:
p[pa] = pb
nonlocal size
size -= 1
n = len(grid)
size = n * n * 4
p = list(range(size))
for i, row in enumerate(grid):
for j, v in enumerate(row):
k = i * n + j
if i < n - 1:
union(4 * k + 2, (k + n) * 4)
if j < n - 1:
union(4 * k + 1, (k + 1) * 4 + 3)
if v == '/':
union(4 * k, 4 * k + 3)
union(4 * k + 1, 4 * k + 2)
elif v == '\\':
union(4 * k, 4 * k + 1)
union(4 * k + 2, 4 * k + 3)
else:
union(4 * k, 4 * k + 1)
union(4 * k + 1, 4 * k + 2)
union(4 * k + 2, 4 * k + 3)
return sizeComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 959. Regions Cut By Slashes 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
| No. | Problem | Difficulty |
|---|---|---|
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
| 0924 | Minimize Malware Spread | Hard |
| 0928 | Minimize Malware Spread II | Hard |
| 1202 | Smallest String With Swaps | Medium |
| 2368 | Reachable Nodes With Restrictions | Medium |
Frequently asked questions
- How hard is LeetCode 959. Regions Cut By Slashes?
LeetCode 959. Regions Cut By Slashes is rated Medium on LeetCode.
- What is the time complexity of LeetCode 959. Regions Cut By Slashes?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 959. Regions Cut By Slashes?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 959. Regions Cut By Slashes cover?
LeetCode 959. Regions Cut By Slashes is tagged Depth-First Search, Breadth-First Search, Union Find, Array, Hash Table and Matrix on LeetCode.