#1559

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Detect Cycles in 2D Grid

Detect cycles in a 2D character grid using DFS while carefully tracking parent cells to avoid invalid revisits.

array depth first search breadth first search union find matrix

Problem Statement

Given a 2D grid of lowercase letters, determine whether there exists a cycle formed by identical letters. A cycle is a path of length four or more that starts and ends at the same cell, moving only to horizontally or vertically adjacent cells of the same value, without revisiting the immediate previous cell.

Implement a function that receives an m x n character grid and returns true if any valid cycle exists, or false if no cycles are present. Ensure your solution handles grids up to size 500 x 500 efficiently, considering all possible same-value paths.

Examples

Example 1

Input: grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]

Output: true

There are two valid cycles shown in different colors in the image below:

Example 2

Input: grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]

Output: true

There is only one valid cycle highlighted in the image below:

Example 3

Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]]

Output: false

Example details omitted.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 500
grid consists only of lowercase English letters.

Solution Approach

DFS with Parent Tracking

Use depth-first search starting from each unvisited cell, recursively exploring neighbors with the same character. Keep track of the parent cell to avoid immediately revisiting the previous position. Return true immediately when a previously visited cell (not the parent) is encountered, indicating a valid cycle.

Iterate Over Entire Grid

Loop through every cell in the grid to ensure no cycle is missed. For each unvisited cell, invoke the DFS routine. This ensures all connected components are checked for cycles and prevents missing isolated cycles in separate areas of the grid.

Early Exit and State Marking

Mark cells as visited during DFS to avoid repeated work. Exit early as soon as a cycle is detected to improve performance. Carefully maintain visited states to differentiate between the current DFS path and previous searches to avoid false positives.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(m n) in the worst case because each cell is visited at most once in DFS. Space complexity is O(m n) for the visited matrix and recursion stack for DFS in a fully connected component.

What Interviewers Usually Probe

They may emphasize handling the 'parent' to prevent invalid 2-cell backtracking.
Expect questions about time and space trade-offs for DFS versus BFS in grids.
They might probe how the solution scales when m and n approach 500.

Common Pitfalls or Variants

Common pitfalls

Failing to track the parent cell can falsely detect a 2-cell back-and-forth as a cycle.
Not iterating over all unvisited cells may miss cycles in disconnected areas.
Reusing the visited matrix incorrectly can create false positives or miss valid cycles.

Follow-up variants

Detect cycles in a 3D grid of characters using the same DFS pattern extended to six directions.
Find cycles of arbitrary lengths with different movement rules like diagonal adjacency.
Return the actual cycle path instead of just true/false, using DFS path reconstruction.

FAQ

What is the main strategy to detect cycles in a 2D grid?

Use depth-first search while tracking the parent cell to avoid revisiting the immediate previous cell, returning true if a cycle is found.

Can cycles be diagonal or only horizontal and vertical?

Cycles must only move horizontally or vertically between adjacent same-value cells; diagonals are not considered.

Why is parent tracking critical in this problem?

Without parent tracking, a DFS might consider an immediate back-and-forth as a valid cycle, which violates the length-4 minimum rule.

Does GhostInterview suggest DFS over BFS for this problem?

Yes, DFS is preferred due to natural recursion and parent tracking, making cycle detection straightforward in connected components.

What is the largest grid size this approach can handle efficiently?

The DFS solution with proper visited tracking efficiently handles grids up to 500 x 500, which meets the problem constraints.

terminal

Solution

Solution 1: BFS

We can traverse each cell in the 2D grid. For each cell, if the cell $grid[i][j]$ has not been visited, we start a breadth-first search (BFS) from that cell. During the search, we need to record the parent node of each cell and the coordinates of the previous cell. If the value of the next cell is the same as the current cell, and it is not the previous cell, and it has already been visited, then it indicates the presence of a cycle, and we return $\textit{true}$. After traversing all cells, if no cycle is found, we return $\textit{false}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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

Solution 2: DFS

We can traverse each cell in the 2D grid. For each cell, if the cell $grid[i][j]$ has not been visited, we start a depth-first search (DFS) from that cell. During the search, we need to record the parent node of each cell and the coordinates of the previous cell. If the value of the next cell is the same as the current cell, and it is not the previous cell, and it has already been visited, then it indicates the presence of a cycle, and we return $\textit{true}$. After traversing all cells, if no cycle is found, we return $\textit{false}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

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

Continue Practicing

#1631 path with minimum effort #1391 check if there is a valid path in a grid #1267 count servers that communicate