Detect Cycles in 2D Grid solution and explanation
Google
9 more videos on this problem
Detect Cycles in 2D Grid | Multiple Ways to Solve | Simplified Explanation | Leetcode 1559 | MIKcodestorywithMIK · 26:00 · 5K views
LeetCode 1559 Detect Cycles in 2D Grid - Java Solution Using BFS Explained With ExamplesAlgorithmicIQ · 23:00 · 2K views
Detect Cycles in 2D Grid | LeetCode | BiWeekly Contest 33 | DFS | GridCP Addict · 8:57 · 2K views
1559. Detect Cycles in 2D Grid (Leetcode Hard)Programming Live with Larry · 12:55 · 2K views
LeetCode 1559. [HARD] Detect Cycles in 2D GridFrancesco Manicardi · 5:27 · 1K views
1559. Detect Cycles in 2D Grid | Leetcode Daily - PythonLeetcode Daily · 5:09 · 431 views
Detect Cycles in 2D Grid | LeetCode 1559 🔥 | Graph + BFS Intuition Explained Study Placement · 23:05 · 357 views
Daily Leetcode #2217: Apr 26, 2026 - 1559. Detect Cycles in 2D GridProgramming Live with Larry · 17:24 · 355 views
Leetcode 1559. Detect Cycles in 2D Grid (union find)LetsCode · 11:22 · 320 views
Detect Cycles in 2D Grid | LeetCode 1559 - Pythonimpoldev · 8:32 · 312 views
The 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:
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.
def containsCycle(grid):
def dfs(x, y, px, py):
if visited[x][y]:
return True
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 < m and 0 <= ny < n and (nx != px or ny != py) and grid[nx][ny] == grid[x][y]:
if dfs(nx, ny, x, y):
return True
return False
if not grid:
return False
m, n = len(grid), len(grid[0])
visited = [[False] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if not visited[i][j]:
if dfs(i, j, -1, -1):
return True
return Falsefunction containsCycle(grid) {
const m = grid.length;
const n = grid[0].length;
const visited = Array.from({ length: m }, () => Array(n).fill(false));
const dfs = (x, y, px, py) => {
if (visited[x][y]) return true;
visited[x][y] = true;
for (const [dx, dy] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
const nx = x + dx;
const ny = y + dy;
if (nx >= 0 && ny >= 0 && nx < m && ny < n && !(nx === px && ny === py) && grid[nx][ny] === grid[x][y]) {
if (dfs(nx, ny, x, y)) return true;
}
}
return false;
};
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (!visited[i][j]) {
if (dfs(i, j, -1, -1)) return true;
}
}
}
return false;
}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.
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.
class Solution {
public boolean containsCycle(char[][] grid) {
int m = grid.length, n = grid[0].length;
int[] parent = new int[m * n];
for (int i = 0; i < m * n; i++) parent[i] = i;
int find(int i) {
if (parent[i] != i) parent[i] = find(parent[parent[i]]);
return parent[i];
}
boolean union(int i, int j) {
int pi = find(i), pj = find(j);
if (pi == pj) return true;
parent[pj] = pi;
return false;
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int current = i * n + j;
if (i > 0 && grid[i][j] == grid[i - 1][j]) {
if (union(current, current - n)) return true;
}
if (j > 0 && grid[i][j] == grid[i][j - 1]) {
if (union(current, current - 1)) return true;
}
}
}
return false;
}
}#include <vector>
#include <numeric>
class Solution {
public:
bool containsCycle(std::vector<std::vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
std::vector<int> parent(m * n);
std::iota(parent.begin(), parent.end(), 0);
auto find = [&](int i) {
if (parent[i] != i) parent[i] = find(parent[i]);
return parent[i];
};
auto unite = [&](int i, int j) {
int pi = find(i), pj = find(j);
if (pi == pj) return true;
parent[pj] = pi;
return false;
};
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (i > 0 && grid[i][j] == grid[i - 1][j]) {
if (unite(i * n + j, (i - 1) * n + j)) return true;
}
if (j > 0 && grid[i][j] == grid[i][j - 1]) {
if (unite(i * n + j, i * n + j - 1)) return true;
}
}
}
return false;
}
};The Java solution also uses a Union-Find structure. We initialize each cell's parent to itself, and try to unify adjacent cells with the same value. Detection of an unsuccessful union due to a shared parent indicates a cycle.
Time Complexity: O(m * n), nearly constant time by using optimizations like path compression.
Space Complexity: O(m * n) due to the parent array.
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.
function containsCycle(grid: string[][]): boolean {
const [m, n] = [grid.length, grid[0].length];
const vis: boolean[][] = Array.from({ length: m }, () => Array(n).fill(false));
const dirs = [-1, 0, 1, 0, -1];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (!vis[i][j]) {
const q: [number, number, number, number][] = [[i, j, -1, -1]];
vis[i][j] = true;
for (const [x, y, px, py] of q) {
for (let k = 0; k < 4; k++) {
const [nx, ny] = [x + dirs[k], y + dirs[k + 1]];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] !== grid[x][y] || (nx === px && ny === py)) {
continue;
}
if (vis[nx][ny]) {
return true;
}
q.push([nx, ny, x, y]);
vis[nx][ny] = true;
}
}
}
}
}
}
return false;
}func containsCycle(grid [][]byte) bool {
m, n := len(grid), len(grid[0])
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
dirs := []int{-1, 0, 1, 0, -1}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if !vis[i][j] {
q := [][]int{{i, j, -1, -1}}
vis[i][j] = true
for len(q) > 0 {
p := q[0]
q = q[1:]
x, y, px, py := p[0], p[1], p[2], p[3]
for k := 0; k < 4; k++ {
nx, ny := x+dirs[k], y+dirs[k+1]
if nx >= 0 && nx < m && ny >= 0 && ny < n {
if grid[nx][ny] != grid[x][y] || (nx == px && ny == py) {
continue
}
if vis[nx][ny] {
return true
}
q = append(q, []int{nx, ny, x, y})
vis[nx][ny] = true
}
}
}
}
}
}
return false
}impl Solution {
pub fn contains_cycle(grid: Vec<Vec<char>>) -> bool {
let m = grid.len();
let n = grid[0].len();
let mut vis = vec![vec![false; n]; m];
let dirs = vec![-1, 0, 1, 0, -1];
for i in 0..m {
for j in 0..n {
if !vis[i][j] {
let mut q = vec![(i as isize, j as isize, -1, -1)];
vis[i][j] = true;
while !q.is_empty() {
let (x, y, px, py) = q.pop().unwrap();
for k in 0..4 {
let nx = x + dirs[k];
let ny = y + dirs[k + 1];
if nx >= 0 && nx < m as isize && ny >= 0 && ny < n as isize {
let nx = nx as usize;
let ny = ny as usize;
if grid[nx][ny] != grid[x as usize][y as usize]
|| (nx == px as usize && ny == py as usize)
{
continue;
}
if vis[nx][ny] {
return true;
}
q.push((nx as isize, ny as isize, x, y));
vis[nx][ny] = true;
}
}
}
}
}
}
false
}
}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.
function containsCycle(grid: string[][]): boolean {
const [m, n] = [grid.length, grid[0].length];
const vis: boolean[][] = Array.from({ length: m }, () => Array(n).fill(false));
const dfs = (x: number, y: number, px: number, py: number): boolean => {
vis[x][y] = true;
const dirs = [-1, 0, 1, 0, -1];
for (let k = 0; k < 4; k++) {
const [nx, ny] = [x + dirs[k], y + dirs[k + 1]];
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (grid[nx][ny] !== grid[x][y] || (nx === px && ny === py)) {
continue;
}
if (vis[nx][ny] || dfs(nx, ny, x, y)) {
return true;
}
}
}
return false;
};
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (!vis[i][j] && dfs(i, j, -1, -1)) {
return true;
}
}
}
return false;
}func containsCycle(grid [][]byte) bool {
m, n := len(grid), len(grid[0])
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
dirs := []int{-1, 0, 1, 0, -1}
var dfs func(x, y, px, py int) bool
dfs = func(x, y, px, py int) bool {
vis[x][y] = true
for k := 0; k < 4; k++ {
nx, ny := x+dirs[k], y+dirs[k+1]
if nx >= 0 && nx < m && ny >= 0 && ny < n {
if grid[nx][ny] != grid[x][y] || (nx == px && ny == py) {
continue
}
if vis[nx][ny] || dfs(nx, ny, x, y) {
return true
}
}
}
return false
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if !vis[i][j] && dfs(i, j, -1, -1) {
return true
}
}
}
return false
}impl Solution {
pub fn contains_cycle(grid: Vec<Vec<char>>) -> bool {
let m = grid.len();
let n = grid[0].len();
let mut vis = vec![vec![false; n]; m];
let dirs = vec![-1, 0, 1, 0, -1];
fn dfs(
x: usize,
y: usize,
px: isize,
py: isize,
grid: &Vec<Vec<char>>,
vis: &mut Vec<Vec<bool>>,
dirs: &Vec<isize>,
) -> bool {
vis[x][y] = true;
for k in 0..4 {
let nx = (x as isize + dirs[k]) as usize;
let ny = (y as isize + dirs[k + 1]) as usize;
if nx < grid.len() && ny < grid[0].len() {
if grid[nx][ny] != grid[x][y] || (nx as isize == px && ny as isize == py) {
continue;
}
if vis[nx][ny] || dfs(nx, ny, x as isize, y as isize, grid, vis, dirs) {
return true;
}
}
}
false
}
for i in 0..m {
for j in 0..n {
if !vis[i][j] && dfs(i, j, -1, -1, &grid, &mut vis, &dirs) {
return true;
}
}
}
false
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Depth First Search for Cycle Detection | Time Complexity: Space Complexity: |
| Union-Find Algorithm for Cycle Detection | Time Complexity: Space Complexity: |
| BFS | – |
| DFS | – |
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. |
Frequently asked questions
Is Detect Cycles in 2D Grid easy or hard?
Detect Cycles in 2D Grid is classified as a Medium difficulty problem. The challenge lies in modeling the grid as a graph and correctly handling parent tracking during traversal to avoid false positives while still detecting real cycles.
Detect Cycles in 2D Grid Python/Java solution
Python and Java implementations usually rely on DFS with a visited matrix and parent coordinates passed during recursion. The algorithm checks four directions and continues only when the character matches. Union-Find solutions are also common in Java and C++ using path compression and union by rank.
How to solve Detect Cycles in 2D Grid in O(n)?
Treat the grid as a graph and run DFS from each unvisited cell. Track the previous cell coordinates so the traversal does not count the immediate parent as a cycle. Each cell is processed once, producing O(m*n) time complexity and O(m*n) space for the visited structure.
What is the best approach for Detect Cycles in 2D Grid?
Depth-First Search (DFS) with parent tracking is the most common solution. Each cell explores its neighbors with the same character while keeping track of the previous cell to avoid false cycle detection. If DFS reaches an already visited cell that is not the parent, a cycle exists. The algorithm runs in O(m*n) time.
Is Detect Cycles in 2D Grid asked at Google/Amazon/Meta?
Cycle detection in grids and graphs frequently appears in interviews at companies like Google, Amazon, and Meta. Variations include detecting cycles in undirected graphs, islands problems, and grid connectivity questions. This problem specifically tests DFS traversal and graph modeling skills.
What data structure is used in Detect Cycles in 2D Grid?
The problem typically uses graph traversal structures such as recursion stacks or explicit stacks for DFS along with a visited matrix. Another common approach uses the Union-Find (Disjoint Set Union) data structure to track connected components and detect cycles when merging sets.
What is the time complexity of Detect Cycles in 2D Grid?
The optimal solutions run in O(m*n) time where m and n are grid dimensions. DFS visits each cell once while checking up to four neighbors. Union-Find also processes each cell with near-constant union and find operations, resulting in O(m*n * α(n)).