Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Connect neighboring cells only when their characters match. A cycle in this undirected graph is detected when traversal reaches an already visited cell through an edge other than the one leading back to its parent. Ignoring that parent edge prevents falsely treating a single connection as a cycle.

Approach

Start a DFS from every still-unvisited cell, restricting traversal to its character. Record visits and carry the previous cell's coordinates. For each in-bounds neighbor other than the parent, continue only if its character matches; encountering a previously visited matching cell establishes a cycle. Return false if every component finishes without one. The four-neighbor grid has no triangular cycles, so a genuine cycle automatically has at least four cells. Python uses recursion and JavaScript an explicit DFS stack.

class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        n = len(grid)
        m = len(grid[0])

        def dfs(i, j, pi, pj, c):
            if grid[i][j] != c: return False
            if (i, j) in seen: return True
            seen.add((i, j))

            for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
                if ni < 0 or ni == n or nj < 0 or nj == m or (ni, nj) == (pi, pj): continue
                if dfs(ni, nj, i, j, c): return True
            
            return False
        
        seen = set()
        for i in range(n):
            for j in range(m):
                if not (i, j) in seen:
                    if dfs(i, j, -1, -1, grid[i][j]): return True
        
        return False

Complexity analysis

For an R by C grid, each cell is expanded at most once and checks four neighbors, giving O(RC) time and O(RC) auxiliary space for visited state and traversal storage. JavaScript uses an explicit stack. Python uses recursive DFS, whose depth can be O(RC); legal large components can exceed the default recursion limit unless the runner raises it sufficiently.