Problem Description

Given a 2D grid of characters, your task is to determine if there exists a cycle in the grid. 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, and only traverses cells with the same character. Additionally, you cannot immediately revisit the cell you just came from (i.e., no immediate backtracking). Each movement must stay within the bounds of the grid.

• The grid is given as a list of lists (or 2D array) of characters grid.
• You must return true if there is at least one such cycle, false otherwise.
• You cannot reuse the same cell within a single path except for starting/ending the cycle.
• Key constraints: Grid size up to 500x500, so efficiency matters.

Thought Process

At first glance, the problem resembles the classic "cycle detection" in graphs, but applied to a 2D grid where each cell is a node, and edges exist between adjacent (up/down/left/right) cells of the same character.

A naive brute-force solution would try every possible path from every cell, but this is computationally infeasible for large grids. Instead, we realize that the problem can be reduced to cycle detection in an undirected graph, with the twist that we can only move to cells of the same character and must not immediately backtrack.

The standard approach for cycle detection in undirected graphs is to use Depth-First Search (DFS), keeping track of the parent node to avoid trivial cycles. If during DFS we reach a previously visited cell that isn't the parent, and the path length is at least 4, we've found a valid cycle.

Solution Approach

Here's how we solve the problem efficiently:

1. Model the grid as a graph: Each cell is a node. There are edges between adjacent cells (up, down, left, right) with the same character.
2. DFS with parent tracking: For each unvisited cell, start a DFS. When moving to a neighbor, pass the current cell as its "parent." If we visit a cell that's already visited and it's not the parent, and our path is long enough (length ≥ 4), we've found a cycle.
3. Efficient marking: Use a 2D boolean array to mark visited cells. Since cycles can be found from any starting cell, make sure to start DFS from all unvisited cells.
4. Pruning: Only move to neighbors with the same character, and do not move immediately back to the parent cell.
5. Early exit: As soon as a cycle is found, return true.

This approach ensures we do not revisit the same state, and the parent tracking prevents false positives due to immediate backtracking.

Example Walkthrough

Sample Input:

  grid = [
    ['a', 'a', 'a', 'a'],
    ['a', 'b', 'b', 'a'],
    ['a', 'b', 'b', 'a'],
    ['a', 'a', 'a', 'a']
  ]
  

Step-by-step:

• Start DFS from (0,0) with character 'a'.
• Move to (0,1), (1,0), etc. following only adjacent 'a's.
• As we traverse the border, after a few moves, we'll reach a cell already visited (not the parent), and the path length is ≥ 4.
• This forms a cycle around the border of the grid.
• Return true as soon as the cycle is detected.

Time and Space Complexity

Brute-force approach: Trying all possible paths from every cell would be exponential in the number of cells, which is infeasible for large grids.

Optimized DFS approach:

• Time Complexity: O(n * m), where n and m are the grid's dimensions. Each cell is visited at most once for each character component.
• Space Complexity: O(n * m) for the visited array and recursion stack in the worst case.

This is efficient enough for the problem's constraints.

Summary

The key insight is to model the problem as cycle detection in an undirected graph where each cell is a node, and edges exist only between adjacent cells of the same character. By using DFS with parent tracking, we efficiently find cycles of length 4 or more without redundant computation. This approach leverages classic graph theory concepts, adapted to the 2D grid setting, making the solution both elegant and performant.

Code Implementation

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

        def dfs(x, y, from_x, from_y, char, depth):
            if visited[x][y]:
                return depth >= 4
            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<n and 0<=ny<m and grid[nx][ny]==char:
                    if (nx,ny) == (from_x, from_y):
                        continue
                    if dfs(nx, ny, x, y, char, depth+1):
                        return True
            return False

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

class Solution {
public:
    int n, m;
    vector<vector<bool>> visited;
    vector<vector<char>> grid;

    bool dfs(int x, int y, int px, int py, char ch, int depth) {
        if (visited[x][y]) return depth >= 4;
        visited[x][y] = true;
        int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int d = 0; d < 4; ++d) {
            int nx = x + dirs[d][0], ny = y + dirs[d][1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == ch) {
                if (nx == px && ny == py) continue;
                if (dfs(nx, ny, x, y, ch, depth + 1)) return true;
            }
        }
        return false;
    }

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

class Solution {
    int n, m;
    boolean[][] visited;
    char[][] grid;

    boolean dfs(int x, int y, int px, int py, char ch, int depth) {
        if (visited[x][y]) return depth >= 4;
        visited[x][y] = true;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] dir : dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == ch) {
                if (nx == px && ny == py) continue;
                if (dfs(nx, ny, x, y, ch, depth + 1)) return true;
            }
        }
        return false;
    }

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

var containsCycle = function(grid) {
    const n = grid.length, m = grid[0].length;
    const visited = Array.from({length: n}, () => Array(m).fill(false));

    function dfs(x, y, px, py, ch, depth) {
        if (visited[x][y]) return depth >= 4;
        visited[x][y] = true;
        for (const [dx, dy] of [[-1,0],[1,0],[0,-1],[0,1]]) {
            const nx = x + dx, ny = y + dy;
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] === ch) {
                if (nx === px && ny === py) continue;
                if (dfs(nx, ny, x, y, ch, depth + 1)) return true;
            }
        }
        return false;
    }

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