MediumNo. 1559
Detect Cycles in 2D Grid — LeetCode 1559 Python Solution
- Pattern
- Union-Find
- Topics
- Depth-First Search, Breadth-First Search, Union Find, Array, Matrix
- Reading time
- 4 min
- Source
- leetcode.com
The problem
Given a 2D array of characters grid of size m x n, you need to find if there exists any cycle consisting of the same value in grid. A cycle is a path of length 4 or more in the grid that starts and ends at the same cell.
Example
- Input
- grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
- Output
- true
- Explanation
- There are two valid cycles shown in different colors in the image below:
Python solution
class Solution:
def containsCycle(self, grid: List[List[str]]) -> bool:
m, n = len(grid), len(grid[0])
vis = [[False] * n for _ in range(m)]
dirs = (-1, 0, 1, 0, -1)
for i, row in enumerate(grid):
for j, x in enumerate(row):
if vis[i][j]:
continue
vis[i][j] = True
q = [(i, j, -1, -1)]
while q:
x, y, px, py = q.pop()
for dx, dy in pairwise(dirs):
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n:
if grid[nx][ny] != grid[i][j] or (nx == px and ny == py):
continue
if vis[nx][ny]:
return True
vis[nx][ny] = True
q.append((nx, ny, x, y))
return FalseComplexity
- Time
- O(m × n)
- Space · auxiliary
- O(m × n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1559. Detect Cycles in 2D Grid 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 |
|---|---|---|
| 0130 | Surrounded Regions | Medium |
| 0200 | Number of Islands | Medium |
| 0695 | Max Area of Island | Medium |
| 0827 | Making A Large Island | Hard |
| 1020 | Number of Enclaves | Medium |
| 1254 | Number of Closed Islands | Medium |
Frequently asked questions
- How hard is LeetCode 1559. Detect Cycles in 2D Grid?
LeetCode 1559. Detect Cycles in 2D Grid is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1559. Detect Cycles in 2D Grid?
The Python solution on this page runs in O(m × n).
- What is the space complexity of LeetCode 1559. Detect Cycles in 2D Grid?
The Python solution on this page uses O(m × n) auxiliary space.
- What topics does LeetCode 1559. Detect Cycles in 2D Grid cover?
LeetCode 1559. Detect Cycles in 2D Grid is tagged Depth-First Search, Breadth-First Search, Union Find, Array and Matrix on LeetCode.