Watch 8 video solutions for Detect Cycles in 2D Grid, a medium level problem involving Array, Depth-First Search, Breadth-First Search. This walkthrough by AlgorithmicIQ has 2,573 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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:
Example 2:
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:
Example 3:
Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]] Output: false
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 500grid consists only of lowercase English letters.Problem Overview: You are given an m x n grid of characters. The task is to detect whether a cycle exists where adjacent cells (up, down, left, right) contain the same character and form a loop of length ≥ 4 without immediately revisiting the previous cell.
Approach 1: Depth-First Search for Cycle Detection (O(m*n) time, O(m*n) space)
This approach treats the grid as a graph where each cell connects to its four neighbors if they contain the same character. Run Depth-First Search from every unvisited cell and pass the previous cell coordinates to avoid falsely detecting the edge you just came from as a cycle. During DFS, if you reach a cell that was already visited and it is not the parent, a cycle exists. A boolean visited matrix tracks explored cells. Each cell is processed once, giving O(m*n) time complexity and O(m*n) space due to recursion stack and visited storage. This method directly models graph traversal and is straightforward to implement for grid-based cycle detection.
Approach 2: Union-Find Algorithm for Cycle Detection (O(m*n * α(n)) time, O(m*n) space)
This method uses the Union-Find (Disjoint Set Union) structure to track connected components of cells with the same character. Iterate through the grid and attempt to union each cell with its right and bottom neighbors if the characters match. Before performing the union, check whether both cells already share the same root. If they do, connecting them again would create a cycle. Path compression and union by rank keep operations nearly constant time, resulting in O(m*n * α(n)) complexity where α is the inverse Ackermann function. This approach works well when you want a reusable connectivity structure across the entire matrix.
Recommended for interviews: DFS is usually the expected solution. It demonstrates understanding of graph traversal and parent tracking in cycle detection. Union-Find also achieves optimal complexity and shows strong knowledge of connected-component algorithms, but DFS tends to be easier to explain and implement under interview time constraints.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search (DFS) | O(m*n) | O(m*n) | Best general solution for grid cycle detection. Easy to implement and commonly expected in interviews. |
| Union-Find (Disjoint Set) | O(m*n * α(n)) | O(m*n) | Useful when modeling connected components or when multiple connectivity checks are required. |