Detect Cycles in 2D Grid - Solution & Explanation
Problem Statement
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 <= 500gridconsists only of lowercase English letters.
Approach Overview
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 1: Depth First Search for Cycle Detection
This approach uses Depth First Search (DFS) to detect cycles in the grid. We treat the grid as an unweighted graph and use DFS to explore each cell. For each unvisited cell, we start a DFS traversal and check for cycles.
We can move to adjacent cells if they have the same value and haven't been visited in the current DFS path or backtrack directly to the previously visited cell.
The containsCycle function starts by defining a dfs helper function that performs depth-first search. If we find a visited cell during the search, a cycle exists and we return True.
We iterate over each unvisited cell in grid, initiating a DFS from there. We avoid moving back to the immediate previous cell by using parameters px and py in the DFS.
If we complete the search with no cycles found, the function returns False.
Code
Python
JavaScript
Complexity
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited once.
Space Complexity: O(m * n) for the visited list to keep track of visited cells.
Approach 2: Union-Find Algorithm for Cycle Detection
This approach uses the Union-Find (or Disjoint Set Union) method to detect cycles in the grid. We treat each cell as a node and union cells with the same value that are adjacent. If we encounter cells from the same set being attempted to union, a cycle is detected.
This C++ solution employs the Union-Find algorithm combining find and unite operations. Each cell in the grid is treated as a node in a disjoint-set forest. Incompatible unions imply a cycle exists, and we return true.
Complexity
Time Complexity: Approximately O(m * n) with union by rank and path compression combined.
Space Complexity: O(m * n) for the disjoint-set data structure.
Approach 3: BFS
We can traverse each cell in the 2D grid. For each cell, if the cell grid[i][j] has not been visited, we start a breadth-first search (BFS) from that cell. During the search, we need to record the parent node of each cell and the coordinates of the previous cell. If the value of the next cell is the same as the current cell, and it is not the previous cell, and it has already been visited, then it indicates the presence of a cycle, and we return true. After traversing all cells, if no cycle is found, we return false.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the 2D grid, respectively.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Approach 4: DFS
We can traverse each cell in the 2D grid. For each cell, if the cell grid[i][j] has not been visited, we start a depth-first search (DFS) from that cell. During the search, we need to record the parent node of each cell and the coordinates of the previous cell. If the value of the next cell is the same as the current cell, and it is not the previous cell, and it has already been visited, then it indicates the presence of a cycle, and we return true. After traversing all cells, if no cycle is found, we return false.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the 2D grid, respectively.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Depth First Search for Cycle Detection | Time Complexity: Space Complexity: |
| Union-Find Algorithm for Cycle Detection | Time Complexity: Approximately Space Complexity: |
| BFS | — |
| DFS | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Detect Cycles in 2D Grid | Multiple Ways to Solve | Simplified Explanation | Leetcode 1559 | MIK • codestorywithMIK • 5,584 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Detect Cycles in 2D Grid easy or hard?
Detect Cycles in 2D Grid Python/Java solution
How to solve Detect Cycles in 2D Grid in O(n)?
What is the best approach for Detect Cycles in 2D Grid?
Is Detect Cycles in 2D Grid asked at Google/Amazon/Meta?
What data structure is used in Detect Cycles in 2D Grid?
What is the time complexity of Detect Cycles in 2D Grid?
Ready to solve this problem?
Practice Detect Cycles in 2D Grid with our built-in code editor and test cases.
Practice on FleetCode