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.In #1559 Detect Cycles in 2D Grid, the goal is to determine whether a grid of characters contains a cycle formed by adjacent cells with the same character. A cycle exists if you can start from a cell and return to it after moving through at least four connected cells without revisiting the immediate parent.
A common strategy is to use Depth-First Search (DFS). Traverse each unvisited cell and recursively explore its four directions. While exploring, keep track of the previous cell so you don’t count the parent as a cycle. If you encounter a previously visited cell with the same character that is not the parent, a cycle exists.
Alternatively, Breadth-First Search (BFS) can perform a similar traversal using a queue. Another efficient technique is Union-Find, where neighboring cells with the same value are unioned, and detecting a union between already connected nodes signals a cycle.
These approaches typically run in O(m × n) time since each cell is processed a constant number of times.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Depth-First Search (DFS) | O(m × n) | O(m × n) |
| Breadth-First Search (BFS) | O(m × n) | O(m × n) |
| Union-Find | O(m × n * α(n)) | O(m × n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Keep track of the parent (previous position) to avoid considering an invalid path.
Use DFS or BFS and keep track of visited cells to see if there is a cycle.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of grid cycle detection appear in technical interviews at large tech companies. These problems test graph traversal skills, grid modeling, and understanding of DFS, BFS, or Union-Find techniques.
DFS or BFS typically uses a visited matrix and recursion stack or queue to track traversal. Alternatively, a Union-Find (Disjoint Set) structure can efficiently detect cycles when merging adjacent cells with the same value.
The most common optimal approach is using Depth-First Search (DFS). By tracking visited cells and the parent cell during traversal, you can detect when a previously visited cell with the same character is reached again, indicating a cycle.
Tracking the parent cell prevents falsely identifying the immediate previous step as a cycle. Since grid traversal moves back and forth between neighbors, ignoring the parent ensures only true loops are detected.