Problem 23.5 · Cycle DetectionMedium

Detect Cycles in 2D Grid

What it teaches: Undirected cycle detection on an implicit grid graph, remembering the parent cell.

Practise it on judges as “Detect Cycles in 2D Grid”.

The problem

Return true if the grid contains a cycle of length ≥ 4 made of cells with the same letter, moving up/down/left/right and never immediately going back to the cell you came from.

Example 1

Input: grid = [[a,a,a,a],[a,b,b,a],[a,b,b,a],[a,a,a,a]]
Output: true

Constraints

1 ≤ rows, cols ≤ 500

Pattern clues in the wording

→ Cycle in an undirected graph of same-valued cells

These clues point to Graph BFS: Explore from a start node in rings of increasing distance using a queue and a visited set.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public boolean containsCycle(char[][] grid) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]	true
2	grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]	true
3	grid = [["a","b","b"],["b","z","b"],["b","b","a"]]	false

From slow to fast

Approaches

1. BFS with parent · O(rows × cols)

BFS with parent

Time O(rows × cols) Space O(rows × cols)

For each unvisited cell, BFS over same-letter neighbours storing each cell's parent. A visited same-letter neighbour that isn't the parent means a cycle.

Approach 1

import java.util.*;

class Solution {
    public boolean containsCycle(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        boolean[][] seen = new boolean[m][n];
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int sr = 0; sr < m; sr++)
            for (int sc = 0; sc < n; sc++) {
                if (seen[sr][sc]) continue;
                seen[sr][sc] = true;
                Deque<int[]> q = new ArrayDeque<>();
                q.offer(new int[]{sr, sc, -1, -1});           // r, c, parent r, parent c
                while (!q.isEmpty()) {
                    int[] t = q.poll();
                    for (int[] d : dirs) {
                        int r = t[0] + d[0], c = t[1] + d[1];
                        if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] != grid[sr][sc]) continue;
                        if (r == t[2] && c == t[3]) continue;   // the edge we came along
                        if (seen[r][c]) return true;
                        seen[r][c] = true;
                        q.offer(new int[]{r, c, t[0], t[1]});
                    }
                }
            }
        return false;
    }
}

Verdict: Iterative, so no deep recursion on 500 × 500 grids.

Before you submit

Edge cases and common mistakes

Test these inputs

Single row (no cycle possible)
A 2 × 2 block of one letter (cycle of length 4)

Mistakes people make

Not skipping the parent (every edge looks like a cycle).

Interview

Follow-up questions

Why is any cycle found here automatically of length ≥ 4?

Command Palette

The problem

Approaches

BFS with parent

Edge cases and common mistakes

Follow-up questions