LeetCode Solutions Blog

Detect Cycles in 2D Grid

Number: 1663

Difficulty: Medium

Paid? No

Problem Description

Given an m x n grid of lowercase English letters, determine whether there exists a cycle in the grid that consists of the same character. A valid cycle is a path of length 4 or more that starts and ends at the same cell, moves only in four directions (up, down, left, right), and does not immediately reverse the last move.

Key Insights

Use Depth First Search (DFS) to explore connected cells with the same character.
Track the DFS path using a recursion “visited” (or recursion stack) to detect a cycle.
Avoid considering the immediate parent cell in DFS to prevent trivial backtracking.
Use a global visited array to avoid reprocessing nodes from previously explored components.
A cycle is valid only if the path has a length of at least 4.

Space and Time Complexity

Time Complexity: O(m * n) – each cell is processed once. Space Complexity: O(m * n) – for global and recursion visited arrays in the worst-case scenario.

Solution

We solve the problem using DFS. For each cell that has not been globally visited, we perform a recursive DFS that follows adjacent cells with the same character. We maintain a separate 2D array to track cells in the current DFS call (recursion stack). During DFS, if we encounter a cell that is already in the current DFS path (and it isn’t the immediate parent) and the current path length is at least 4, we have found a cycle. After processing a component, we mark all cells visited in that DFS to skip redundant work later.

Code Solutions

# Python solution using DFS with recursion stack tracking
class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        # Global visited array to avoid reprocessing
        globalVisited = [[False] * n for _ in range(m)]
        
        # DFS function that tracks the recursion stack in 'currentVisited'
        def dfs(x, y, fromX, fromY, char, depth, currentVisited):
            # Mark current cell as part of the recursion path
            currentVisited[x][y] = True
            # Explore the four possible directions
            for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
                nx, ny = x + dx, y + dy
                # Check boundaries and same character condition
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == char:
                    # Skip the cell we just came from
                    if nx == fromX and ny == fromY:
                        continue
                    # If the neighbor is already in current DFS and path is long enough, a cycle is found
                    if currentVisited[nx][ny]:
                        if depth >= 3:
                            return True
                    else:
                        if dfs(nx, ny, x, y, char, depth + 1, currentVisited):
                            return True
            return False
        
        # Process each cell that has not been visited globally
        for i in range(m):
            for j in range(n):
                if not globalVisited[i][j]:
                    # Initialize a new recursion visited array for current DFS
                    currentVisited = [[False] * n for _ in range(m)]
                    if dfs(i, j, -1, -1, grid[i][j], 0, currentVisited):
                        return True
                    # Mark all cells reached in this DFS as globally visited
                    for x in range(m):
                        for y in range(n):
                            if currentVisited[x][y]:
                                globalVisited[x][y] = True
        return False