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 \times n).

What is the space complexity of LeetCode 1559. Detect Cycles in 2D Grid?

The Python solution on this page uses O(m \times 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.

Detect Cycles in 2D Grid — LeetCode 1559 Python Solution

MediumDepth-First SearchBreadth-First SearchUnion FindArrayMatrix

Problem: #1559
Pattern: Union-Find
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

Python

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 False

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 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.

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 \times n).
What is the space complexity of LeetCode 1559. Detect Cycles in 2D Grid?: The Python solution on this page uses O(m \times 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.