1559. Detect Cycles in 2D Grid

Array
DFS
BFS
Union Find
Matrix

TIME

O(m * n)

SPACE

O(m * n)

Intuition

Standard cycle detection in an undirected graph. A cycle exists if during DFS we reach a visited cell that is not our immediate parent.

Solution

DFS Approach

def dfs(i, j, pi, pj, char):
    visited[i][j] = True
    
    for ni, nj in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]:
        if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == char:
            if not visited[ni][nj]:
                if dfs(ni, nj, i, j, char):
                    return True
            elif (ni, nj) != (pi, pj):
                # Visited cell that's not parent = cycle!
                return True
    
    return False

Why Track Parent?

In an undirected graph, when we go from A → B, we can immediately go back B → A. This isn't a cycle. We need to detect when we reach a visited node via a different path.

Union-Find Alternative

For each cell, check if adjacent cells with same value are already in the same connected component. If yes → cycle exists.

Complexity

Time: O(m × n)
Space: O(m × n) for visited array and recursion stack

Edge Cases

Single row or column (no cycle possible with length ≥ 4)
All same characters forming a large cycle
No cycles exist

Code

from typing import List


class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        """
        1559. Detect Cycles in 2D Grid
        Time: O(m * n)
        Space: O(m * n)
        """
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]

        def dfs(i: int, j: int, pi: int, pj: int, char: str) -> bool:
            visited[i][j] = True

            for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                ni, nj = i + di, j + dj

                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == char:
                    if not visited[ni][nj]:
                        if dfs(ni, nj, i, j, char):
                            return True
                    elif (ni, nj) != (pi, pj):
                        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

/**
 * 1559. Detect Cycles in 2D Grid
 * Time: O(m * n)
 * Space: O(m * n)
 */
class Solution {
    private int m, n;
    private char[][] grid;
    private boolean[][] visited;
    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public boolean containsCycle(char[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];

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

        return false;
    }

    private boolean dfs(int i, int j, int pi, int pj, char c) {
        visited[i][j] = true;

        for (int[] d : dirs) {
            int ni = i + d[0], nj = j + d[1];

            if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == c) {
                if (!visited[ni][nj]) {
                    if (dfs(ni, nj, i, j, c)) {
                        return true;
                    }
                } else if (ni != pi || nj != pj) {
                    return true;
                }
            }
        }

        return false;
    }
}