Detect Cycles in 2D Grid

medium graph grid dfs cycle detection

Problem

Given a 2D grid of characters, a cycle is a path of length 4 or more that starts and ends at the same cell, moves only up, down, left, or right between cells of the same value, and never revisits a cell on the path. Return true if any such cycle exists.

Inputgrid = [["a","a","a","a"],["a","b","b","a"],["a","a","a","a"]]

Outputtrue

The border of 'a' cells loops back on itself, forming a cycle of length 10.

grid (rows separated by ; cells by ,)

def containsCycle(grid):
    m, n = len(grid), len(grid[0])
    seen = [[False] * n for _ in range(m)]

    def dfs(r, c, pr, pc):
        seen[r][c] = True
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if not (0 <= nr < m and 0 <= nc < n):
                continue
            if grid[nr][nc] != grid[r][c] or (nr == pr and nc == pc):
                continue
            if seen[nr][nc] or dfs(nr, nc, r, c):
                return True
        return False

    for i in range(m):
        for j in range(n):
            if not seen[i][j] and dfs(i, j, -1, -1):
                return True
    return False

function containsCycle(grid) {
  const m = grid.length, n = grid[0].length;
  const seen = Array.from({ length: m }, () => new Array(n).fill(false));
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  function dfs(r, c, pr, pc) {
    seen[r][c] = true;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
      if (grid[nr][nc] !== grid[r][c] || (nr === pr && nc === pc)) continue;
      if (seen[nr][nc] || dfs(nr, nc, r, c)) return true;
    }
    return false;
  }

  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      if (!seen[i][j] && dfs(i, j, -1, -1)) return true;
  return false;
}

boolean[][] seen;
char[][] g;
int m, n;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

boolean dfs(int r, int c, int pr, int pc) {
    seen[r][c] = true;
    for (int[] d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
        if (g[nr][nc] != g[r][c] || (nr == pr && nc == pc)) continue;
        if (seen[nr][nc] || dfs(nr, nc, r, c)) return true;
    }
    return false;
}

boolean containsCycle(char[][] grid) {
    g = grid; m = grid.length; n = grid[0].length;
    seen = new boolean[m][n];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (!seen[i][j] && dfs(i, j, -1, -1)) return true;
    return false;
}

vector<vector<char>> g;
vector<vector<bool>> seen;
int m, n;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

bool dfs(int r, int c, int pr, int pc) {
    seen[r][c] = true;
    for (auto& d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
        if (g[nr][nc] != g[r][c] || (nr == pr && nc == pc)) continue;
        if (seen[nr][nc] || dfs(nr, nc, r, c)) return true;
    }
    return false;
}

bool containsCycle(vector<vector<char>>& grid) {
    g = grid; m = grid.size(); n = grid[0].size();
    seen.assign(m, vector<bool>(n, false));
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (!seen[i][j] && dfs(i, j, -1, -1)) return true;
    return false;
}

Explanation

Treat the grid as a graph: each cell is a node, and an edge joins two orthogonally adjacent cells that hold the same character. A cycle in the problem is exactly an undirected cycle inside one of these same-valued components.

We run a depth-first search from every unvisited cell. The trick is the parent argument (pr, pc): when we explore a neighbour we skip the cell we just came from, so we never count the trivial "step back and forth" as a cycle. Every other neighbour with the same value is a real edge of the component.

While exploring a cell, if we reach a same-valued neighbour that is already seen and is not the parent, we have found a second way into a previously visited node — that closes a loop, so a cycle exists and we return true.

Because each cell is marked seen the first time it is reached and never revisited, the search touches every cell a constant number of times. Marking the parent guarantees we only report genuine cycles of length 4 or more.

In the example the outer ring of a cells forms a closed loop: DFS walks around the border, and when it tries to step onto an already-seen a that is not its parent, the cycle is detected. The same idea can be implemented with union-find — union same-valued neighbours and report a cycle the moment two cells are already in one set.

Time: O(m·n) Space: O(m·n)