LeetCode 1559 - Detect Cycles in 2D Grid

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

Problem Understanding

The problem asks us to detect cycles in a 2D grid of characters where all cells in the cycle must contain the same character. A cycle is defined as a path that starts and ends at the same cell and has a length of four or more. Movement is allowed only in the four cardinal directions: up, down, left, and right. Importantly, you cannot immediately return to the previous cell, meaning a move like (1,1) -> (1,2) -> (1,1) is not a valid cycle.

The input is a 2D array of size m x n with lowercase English letters. The constraints indicate that m and n can be up to 500, which rules out any approach with time complexity higher than O(m*n) for each operation. The output is a boolean: true if any valid cycle exists and false otherwise.

Key edge cases include:

Grids with all identical characters forming large cycles.
Grids with no possible cycles due to either all unique characters or isolated same-character regions.
Small grids where cycles are impossible (like 1xN or Nx1).

Understanding the movement restriction and minimum cycle length is critical to avoid false positives.

Approaches

The brute-force approach would be to start from every cell and try to find all possible paths using DFS or BFS, checking for cycles. While this is conceptually simple, it is extremely inefficient because there could be an exponential number of paths, especially in grids of size up to 500x500.

The optimal approach uses DFS with parent tracking. The idea is to perform a DFS from each unvisited cell and keep track of the previous cell to avoid backtracking to it immediately. If during DFS we reach a visited cell that is not the immediate parent, then we have found a valid cycle. This approach efficiently explores each connected component of identical characters once and guarantees that cycles are detected without revisiting unnecessary paths.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^(m*n))	O(m*n)	Explore all paths; infeasible for large grids
DFS with Parent Tracking	O(m*n)	O(m*n)	Visit each cell once; detect cycles using DFS and parent

Algorithm Walkthrough

Initialize a 2D boolean array visited of size m x n to track visited cells.
Iterate over each cell (i, j) in the grid.
If the cell has not been visited, start a DFS from this cell, passing (-1, -1) as the parent (no parent initially).
In DFS:
Mark the current cell as visited.
Explore all four neighbors (up, down, left, right).
Skip neighbors outside the grid or with a different character.
If a neighbor has already been visited and is not the parent, a cycle exists. Return true.
Otherwise, recursively DFS into the neighbor with the current cell as its parent.
If DFS completes without finding a cycle for all components, return false.

Why it works: The DFS ensures every connected component of the same character is explored. Parent tracking prevents false positives from immediately returning to the previous cell. If a previously visited cell is reached that is not the parent, it confirms a loop of at least length 4 exists.

Python Solution

from typing import List

class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        
        def dfs(x: int, y: int, px: int, py: int, char: str) -> bool:
            visited[x][y] = True
            for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == char:
                    if not visited[nx][ny]:
                        if dfs(nx, ny, x, y, char):
                            return True
                    elif (nx, ny) != (px, py):
                        return True
            return False
        
        for i in range(m):
            for j in range(n):
                if not visited[i][j]:
                    if dfs(i, j, -1, -1, grid[i][j]):
                        return True
        return False

The implementation initializes a visited grid and applies DFS to each unvisited cell. The DFS function recursively explores neighbors and uses parent coordinates (px, py) to avoid backtracking to the immediately previous cell. If it encounters a visited neighbor that is not the parent, a cycle is detected.

Go Solution

func containsCycle(grid [][]byte) bool {
    m, n := len(grid), len(grid[0])
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }

    var dfs func(x, y, px, py int, char byte) bool
    dfs = func(x, y, px, py int, char byte) bool {
        visited[x][y] = true
        directions := [][2]int{{-1,0},{1,0},{0,-1},{0,1}}
        for _, d := range directions {
            nx, ny := x + d[0], y + d[1]
            if nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == char {
                if !visited[nx][ny] {
                    if dfs(nx, ny, x, y, char) {
                        return true
                    }
                } else if nx != px || ny != py {
                    return true
                }
            }
        }
        return false
    }

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if !visited[i][j] {
                if dfs(i, j, -1, -1, grid[i][j]) {
                    return true
                }
            }
        }
    }
    return false
}

The Go solution mirrors the Python implementation, using slices to track visited cells. Recursive DFS handles neighbor exploration, and parent coordinates are used to avoid false cycle detection.

Worked Examples

Example 1:

Input:

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

Starting at (0,0), DFS explores right and down, marking visited cells. Eventually, DFS returns to (0,0) from (0,3) without immediately backtracking, confirming a cycle.

Example 2:

Input:

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

DFS starting at (0,0) explores the c cluster. A previously visited cell (0,2) is reached from (1,2) without being the parent, confirming a cycle.

Example 3:

Input:

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

DFS explores all a and b clusters, but no cell is revisited in a manner that forms a valid cycle, returning false.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m*n)	Each cell is visited once in DFS; neighbor checking is constant time
Space	O(m*n)	Visited array and recursive DFS stack could go up to m*n in worst case

The algorithm scales linearly with the grid size, which is optimal for constraints up to 500x500.

Test Cases

# Provided examples
assert Solution().containsCycle([["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]) == True  # example 1
assert Solution().containsCycle([["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]) == True  # example 2
assert Solution().containsCycle([["a","b","b"],["b","z","b"],["b","b","a"]]) == False  # example 3

# Edge cases
assert Solution().containsCycle([["a"]]) == False  # 1x1 grid, no cycle
assert Solution().containsCycle([["a","a"],["a","a"]]) == True  # minimal 2x2 cycle
assert Solution().containsCycle([["a","b"],["c","d"]]) == False  # no possible cycles
assert Solution().containsCycle([["a"]*500]*500) == True  # large uniform grid

Test	Why
1x1 grid	Confirms algorithm returns False for smallest grid
2x2 uniform grid	Confirms minimal valid cycle detection
2x2 non-uniform grid	Confirms no false positives in small grids