# Detect Cycles in 2D Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/detect-cycles-in-2d-grid)
Canonical: https://scaleengineer.com/dsa/problems/detect-cycles-in-2d-grid
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Matrix
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix)
---
## Problem
Given a 2D array of characters `grid` of size `m x n`, you need to find if there exists any cycle consisting of the **same value** in `grid`.

A cycle is a path of **length 4 or more** in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it - in one of the four directions (up, down, left, or right), if it has the **same value** of the current cell.

Also, you cannot move to the cell that you visited in your last move. For example, the cycle `(1, 1) -> (1, 2) -> (1, 1)` is invalid because from `(1, 2)` we visited `(1, 1)` which was the last visited cell.

Return `true` if any cycle of the same value exists in `grid`, otherwise, return `false`.

**Example 1:**

**![](https://assets.glich.co/dsa/detect-cycles-in-2d-grid/image0.png)**

**Input:** grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
**Output:** true
**Explanation:** There are two valid cycles shown in different colors in the image below:
![](https://assets.glich.co/dsa/detect-cycles-in-2d-grid/image1.png)

**Example 2:**

**![](https://assets.glich.co/dsa/detect-cycles-in-2d-grid/image2.png)**

**Input:** grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
**Output:** true
**Explanation:** There is only one valid cycle highlighted in the image below:
![](https://assets.glich.co/dsa/detect-cycles-in-2d-grid/image3.png)

**Example 3:**

**![](https://assets.glich.co/dsa/detect-cycles-in-2d-grid/image4.png)**

**Input:** grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
**Output:** false

**Constraints:**

* `m == grid.length`
* `n == grid[i].length`
* `1 <= m, n <= 500`
* `grid` consists only of lowercase English letters.

# Approaches
## Depth First Search (DFS)
This approach models the grid as an undirected graph. Each cell `(r, c)` is a node, and an edge exists between two adjacent cells if they contain the same character. The problem then becomes finding a cycle in this graph. We can use Depth First Search (DFS) to traverse the graph and detect cycles. We iterate through every cell of the grid. If a cell hasn't been visited, we start a DFS from it. During the traversal, if we encounter a visited node that is not the immediate parent of the current node in the DFS tree, we have found a back edge, which indicates a cycle.
**Time:** O(m * n), where `m` is the number of rows and `n` is the number of columns. Each cell in the grid is visited at most once during the entire process. · **Space:** O(m * n). This space is used for the `visited` array (O(m * n)) and the recursion call stack. In the worst-case scenario of a path that traverses every cell, the stack depth can be up to O(m * n).
**Pros:** The approach is intuitive and directly translates the problem into a standard graph traversal algorithm.; It is relatively easy to implement using recursion.
**Cons:** The recursive nature can lead to a `StackOverflowError` on very large grids with long, snake-like paths, as the recursion depth can become very large.; The space complexity includes the recursion stack, which can be significant in the worst-case scenario.
### Explanation
To implement this, we'll use a 2D boolean array, `visited`, of the same size as the grid to keep track of visited cells across all traversals. We'll iterate through each cell `(r, c)`. If `visited[r][c]` is false, we start a new DFS traversal for the connected component of cells with the character `grid[r][c]`. 

The DFS function, say `hasCycle(r, c, parent_r, parent_c)`, takes the current cell's coordinates and its parent's coordinates. This parent information is crucial to ensure we don't immediately travel back to the cell we just came from. Inside the DFS, we first mark the current cell as visited. Then, we explore its four neighbors. For any neighbor that has the same character, is not the parent, and has already been visited, we've found a cycle. If a neighbor is valid but unvisited, we recurse on it. If any recursive call finds a cycle, we propagate `true` up the call stack. If the entire grid is scanned and no cycle is found, we return `false`.

The problem states that a cycle must have a length of 4 or more. In a 2D grid where movement is restricted to four directions, the graph formed is bipartite. The smallest possible cycle in a bipartite graph has a length of 4 (e.g., a 2x2 square). Therefore, any cycle detected by this standard algorithm will automatically satisfy the length constraint.

```java
class Solution {
    private int m, n;
    private char[][] grid;
    private boolean[][] visited;
    private int[] dr = {0, 0, 1, -1};
    private int[] dc = {1, -1, 0, 0};

    public boolean containsCycle(char[][] grid) {
        this.m = grid.length;
        this.n = grid[0].length;
        this.grid = grid;
        this.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 r, int c, int pr, int pc, char targetChar) {
        visited[r][c] = true;

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];

            if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == targetChar) {
                if (nr == pr && nc == pc) {
                    continue; // Don't go back to the parent immediately
                }
                if (visited[nr][nc]) {
                    return true; // Found a cycle
                }
                if (dfs(nr, nc, r, c, targetChar)) {
                    return true;
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- Initialize a `visited[m][n]` 2D boolean array, marking all cells as not visited.
- Iterate through each cell `(r, c)` of the grid from `(0, 0)` to `(m-1, n-1)`.
- If the current cell `(r, c)` has not been visited (`visited[r][c]` is false), it signifies the start of a new, unexplored connected component.
- Start a Depth First Search (DFS) from this cell. The DFS function will be of the form `dfs(row, col, parent_row, parent_col)`.
- The `dfs` function:
  1. Marks the current cell `(row, col)` as visited.
  2. Iterates through its four neighbors (up, down, left, right).
  3. For each neighbor `(nr, nc)`:
     a. It must be within the grid boundaries.
     b. It must have the same character as the starting cell of the current component.
     c. It must not be the immediate parent cell from which we arrived at `(row, col)`. This prevents trivial 1-edge-back cycles.
     d. If the neighbor `(nr, nc)` has already been visited (and is not the parent), a cycle has been detected. Return `true`.
     e. If the neighbor is valid but not visited, make a recursive call: `dfs(nr, nc, row, col)`. If this call returns `true`, propagate the result by returning `true` immediately.
- If the DFS completes for a component without finding a cycle, it returns `false`.
- If the main loop finishes checking all cells and components without any DFS returning `true`, then no cycles exist in the grid. Return `false`.

## Breadth First Search (BFS)
Similar to the DFS approach, this method treats the grid as a graph and searches for cycles. However, it uses Breadth First Search (BFS), an iterative traversal algorithm, instead of recursion. By using a queue, BFS explores the graph layer by layer. This avoids the risk of stack overflow that can occur with a deep recursive DFS, making it a more robust solution for very large grids.
**Time:** O(m * n). Each cell is enqueued and processed at most once. · **Space:** O(m * n). This is for the `visited` array and the BFS queue. The queue can, in the worst case, hold a number of elements proportional to the total number of cells.
**Pros:** Being an iterative approach, it is not susceptible to `StackOverflowError`, making it more reliable for large inputs.; BFS is guaranteed to find a shortest path (in terms of number of edges) from the source to any other node, which can be a useful property, although not strictly necessary for this problem.
**Cons:** The queue can grow to a large size, potentially up to O(m * n) elements for certain grid configurations, which might lead to high memory consumption.
### Explanation
The core idea remains the same: traverse connected components of same-valued cells and check for back edges. We use a `visited` array to track visited cells. We iterate through the grid, and for any unvisited cell, we initiate a BFS. The BFS uses a queue to manage the cells to visit. To prevent trivial cycles, we store not just the cell's coordinates in the queue, but also its parent's coordinates (the cell from which it was discovered). When exploring neighbors of a cell, we skip the parent. If we encounter a neighbor that has the same character and has already been visited (and is not the parent), we have found a cycle and can immediately return `true`.

```java
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public boolean containsCycle(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        int[] dr = {0, 0, 1, -1};
        int[] dc = {1, -1, 0, 0};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j]) {
                    if (bfs(i, j, grid, visited, m, n, dr, dc)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    private boolean bfs(int startR, int startC, char[][] grid, boolean[][] visited, int m, int n, int[] dr, int[] dc) {
        char targetChar = grid[startR][startC];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{startR, startC, -1, -1}); // r, c, pr, pc
        visited[startR][startC] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int r = current[0];
            int c = current[1];
            int pr = current[2];
            int pc = current[3];

            for (int i = 0; i < 4; i++) {
                int nr = r + dr[i];
                int nc = c + dc[i];

                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == targetChar) {
                    if (nr == pr && nc == pc) {
                        continue;
                    }
                    if (visited[nr][nc]) {
                        return true; // Cycle detected
                    }
                    visited[nr][nc] = true;
                    queue.offer(new int[]{nr, nc, r, c});
                }
            }
        }
        return false;
    }
}
```
### Algorithm
- Initialize a `visited[m][n]` 2D boolean array to `false`.
- Iterate through each cell `(r, c)` of the grid.
- If `visited[r][c]` is `false`, start a Breadth First Search (BFS) from this cell.
- The BFS process for a component:
  1. Create a queue to store states. Each state will contain the cell's coordinates and its parent's coordinates, e.g., `[row, col, parent_row, parent_col]`.
  2. Add the starting cell `[r, c, -1, -1]` to the queue and mark `visited[r][c]` as `true`.
  3. While the queue is not empty:
     a. Dequeue the current state `[curr_r, curr_c, parent_r, parent_c]`.
     b. Explore the four neighbors `(nr, nc)` of `(curr_r, curr_c)`.
     c. For each valid neighbor (in-bounds, same character):
        i. If the neighbor is the parent `(parent_r, parent_c)`, ignore it.
        ii. If `visited[nr][nc]` is `true`, a cycle is found. Return `true`.
        iii. Otherwise, mark `visited[nr][nc]` as `true` and enqueue the new state `[nr, nc, curr_r, curr_c]`.
- If the main loop completes without any BFS finding a cycle, return `false`.

## Union-Find (Disjoint Set Union)
A highly efficient approach for this problem is to use a Union-Find data structure, also known as a Disjoint Set Union (DSU). This data structure is optimized for tracking connectivity between elements. We treat each cell as an element in a set. We iterate through the grid, and for each cell, we check its neighbors (e.g., to the right and down). If two adjacent cells have the same character, we attempt to `union` their sets. If they are already in the same set (i.e., already connected by some other path), adding an edge between them forms a cycle.
**Time:** O(m * n * α(m * n)), where `α` is the extremely slow-growing Inverse Ackermann function. For all practical purposes, the complexity is considered linear, O(m * n), as `α`'s value is less than 5 for any conceivable input size. · **Space:** O(m * n). This space is required for the `parent` and `rank` arrays of the Union-Find data structure.
**Pros:** Extremely fast, with nearly constant time complexity per operation (amortized) due to path compression and union by rank/size optimizations.; It's an iterative approach, free from recursion depth limitations.; Often has lower constant factors than DFS/BFS, making it one of the most performant solutions in practice for cycle detection.
**Cons:** The underlying logic of why this detects cycles might be less intuitive than a direct graph traversal for those unfamiliar with the Union-Find data structure.; Requires implementing the Union-Find data structure, which is slightly more complex than a simple recursive DFS.
### Explanation
We can flatten the 2D grid coordinates `(r, c)` into a 1D index `r * n + c` to use with a standard Union-Find implementation. The Union-Find data structure will maintain a `parent` array and optionally a `rank` or `size` array for optimization (union by rank/size and path compression).

We iterate through every cell `(r, c)`. To avoid redundant checks, for each cell, we only consider forming edges with its right neighbor `(r, c+1)` and its down neighbor `(r+1, c)`. When considering an edge between two cells, say `u` and `v`, we first use the `find` operation to check if they already belong to the same connected component. If `find(u) == find(v)`, it implies there's already a path between them, and adding the direct edge `(u, v)` closes a loop, forming a cycle. In this case, we return `true`. If they are in different components, we merge them using the `union` operation and continue. If we process the entire grid without finding such a condition, no cycles exist.

```java
class Solution {
    public boolean containsCycle(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        UnionFind uf = new UnionFind(m * n);

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                int currentIndex = r * n + c;

                // Check down neighbor
                if (r + 1 < m && grid[r][c] == grid[r + 1][c]) {
                    int downIndex = (r + 1) * n + c;
                    if (uf.find(currentIndex) == uf.find(downIndex)) {
                        return true;
                    }
                    uf.union(currentIndex, downIndex);
                }

                // Check right neighbor
                if (c + 1 < n && grid[r][c] == grid[r][c + 1]) {
                    int rightIndex = r * n + (c + 1);
                    if (uf.find(currentIndex) == uf.find(rightIndex)) {
                        return true;
                    }
                    uf.union(currentIndex, rightIndex);
                }
            }
        }
        return false;
    }
}

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]); // Path compression
    }

    public void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // Union by rank
            if (rank[rootI] > rank[rootJ]) {
                parent[rootJ] = rootI;
            } else if (rank[rootI] < rank[rootJ]) {
                parent[rootI] = rootJ;
            } else {
                parent[rootJ] = rootI;
                rank[rootI]++;
            }
        }
    }
}
```
### Algorithm
- Create a Union-Find (Disjoint Set Union) data structure for `m * n` elements. Each cell `(r, c)` is mapped to a unique integer index, e.g., `index = r * n + c`.
- Initialize the Union-Find structure such that each element is in its own set.
- Iterate through each cell `(r, c)` of the grid.
- For each cell, check its neighbors in two directions (e.g., right and down) to avoid processing each edge twice.
- **Check right neighbor `(r, c+1)`:**
  - If `c+1` is within bounds and `grid[r][c] == grid[r][c+1]`:
    - Find the representatives (roots) for the sets containing `(r, c)` and `(r, c+1)`.
    - If the representatives are the same, it means the two cells are already connected. Adding this edge creates a cycle. Return `true`.
    - Otherwise, perform a `union` operation on the two cells' sets.
- **Check down neighbor `(r+1, c)`:**
  - If `r+1` is within bounds and `grid[r][c] == grid[r+1][c]`:
    - Find the representatives for `(r, c)` and `(r+1, c)`.
    - If they are the same, a cycle is detected. Return `true`.
    - Otherwise, `union` their sets.
- If the loops complete without finding a cycle, return `false`.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
public
  boolean containsCycle(char[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    p = new int[m * n];
    for (int i = 0; i < p.length; ++i) {
      p[i] = i;
    }
    int[] dirs = {0, 1, 0};
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        for (int k = 0; k < 2; ++k) {
          int x = i + dirs[k];
          int y = j + dirs[k + 1];
          if (x < m && y < n && grid[i][j] == grid[x][y]) {
            if (find(x * n + y) == find(i * n + j)) {
              return true;
            }
            p[find(x * n + y)] = find(i * n + j);
          }
        }
      }
    }
    return false;
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### JavaScript

```javascript
/** * @param {character[][]} grid * @return {boolean} */ var containsCycle = function ( grid ) { const m = grid . length ; const n = grid [ 0 ]. length ; let p = Array . from ({ length : m * n }, ( _ , i ) => i ); function find ( x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } const dirs = [ 0 , 1 , 0 ]; for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 0 ; j < n ; ++ j ) { for ( let k = 0 ; k < 2 ; ++ k ) { const x = i + dirs [ k ]; const y = j + dirs [ k + 1 ]; if ( x < m && y < n && grid [ x ][ y ] == grid [ i ][ j ]) { if ( find ( x * n + y ) == find ( i * n + j )) { return true ; } p [ find ( x * n + y )] = find ( i * n + j ); } } } } return false ; };
```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  bool containsCycle(vector<vector<char>> &grid) {
    int m = grid.size(), n = grid[0].size();
    p.resize(m * n);
    for (int i = 0; i < p.size(); ++i)
      p[i] = i;
    vector<int> dirs = {0, 1, 0};
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        for (int k = 0; k < 2; ++k) {
          int x = i + dirs[k], y = j + dirs[k + 1];
          if (x < m && y < n && grid[x][y] == grid[i][j]) {
            if (find(x * n + y) == find(i * n + j))
              return 1;
            p[find(x * n + y)] = find(i * n + j);
          }
        }
      }
    }
    return 0;
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```

### Python

```python
class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] m, n = len(grid), len(grid[0]) p = list(range(m * n)) for i in range(m): for j in range(n): for a, b in [[0, 1], [1, 0]]: x, y = i + a, j + b if x < m and y < n and grid[x][y] == grid[i][j]: if find(x * n + y) == find(i * n + j): return True p[find(x * n + y)] = find(i * n + j) return False

```