1559. Detect Cycles in 2D Grid

Time: O(m*n)

Space: O(m*n)

Intuition

Treat cells with the same character as an undirected graph where each cell connects to up/down/left/right neighbors of equal value. A cycle exists if during DFS/BFS we reach an already-visited node that is not the parent we came from. Parent tracking is essential because the immediate back-edge to parent should not be counted as a cycle.

Algorithm

1Create a visited matrix of size m x n initialized to false.
2Iterate through every cell (i, j). If unvisited, start DFS from it with parent = (-1, -1).
3In DFS, mark current cell visited and scan 4-direction neighbors.
4Skip neighbors that are out of bounds or have different character.
5Skip the parent neighbor (the cell we came from).
6If a valid same-character neighbor is already visited and is not parent, return true (cycle found).
7Otherwise recurse into unvisited same-character neighbors. If any recursive call returns true, propagate true.
8If all components finish with no such back-edge, return false.

Example Walkthrough

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

1.Start DFS from (0,0) = a and walk through connected a-cells on the border.
2.While exploring, eventually reach a neighbor that is already visited and not the direct parent.
3.This confirms a closed loop in the a-component.
4.Return true immediately.

Output: true

Common Pitfalls

•Without parent coordinates, every undirected edge looks like a false cycle when you step back one cell.
•Only same-character neighbors belong to the same graph component; different letters must be ignored.
•Use iterative DFS/BFS if recursion depth is a concern on very large grids.

1559.cs

public class Solution
{
    // Approach: DFS on same-character components with parent tracking; revisiting a
    // previously seen non-parent neighbor implies a cycle.
    // Time: O(m*n) Space: O(m*n)
    private static readonly int[][] DIRS = new int[][] {
        new int[] {0, 1},
        new int[] {1, 0},
        new int[] {0, -1},
        new int[] {-1, 0}
    };

    public bool ContainsCycle(char[][] grid)
    {
        int m = grid.Length;
        int n = grid[0].Length;
        bool[][] seen = new bool[m][];
        for (int i = 0; i < m; i++)
            seen[i] = new bool[n];

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

        return false;
    }

    private bool Dfs(char[][] grid, int i, int j, int prevI, int prevJ, char c, bool[][] seen)
    {
        seen[i][j] = true;

        foreach (var dir in DIRS)
        {
            int x = i + dir[0];
            int y = j + dir[1];
            if (x < 0 || x == grid.Length || y < 0 || y == grid[0].Length)
                continue;
            if (x == prevI && y == prevJ)
                continue;
            if (grid[x][y] != c)
                continue;
            if (seen[x][y])
                return true;
            if (Dfs(grid, x, y, i, j, c, seen))
                return true;
        }

        return false;
    }
}

Was this solution helpful?