Detect Cycles in 2D Grid
Detect Cycles in 2D Grid is a medium graphs problem solved with the cycle detection pattern.
The best approach, optimal (union-find on grid edges), runs in O(m · n · α(m · n)) time and O(m · n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from bfs with parent tracking up.
Problem
You are given an m × n grid of lowercase letters. From a cell you may move to an adjacent cell (up, down, left or right) only if it holds the same letter.
A cycle is a path of length 4 or more that starts and ends at the same cell, moves only between equal letters, and never steps straight back to the cell it just came from. Return true if the grid contains any cycle, otherwise false.
Examples
Example 1
- Input
grid = [["x","x","x"],["x","y","x"],["x","x","x"]]- Output
true- Why
- The eight x cells around the middle form a closed loop.
Example 2
- Input
grid = [["p","p","q"],["q","p","p"],["q","q","p"]]- Output
false- Why
- The p cells form a staircase path and the q cells form small paths; none of them closes into a loop.
Example 3
- Input
grid = [["k","k"],["k","k"]]- Output
true- Why
- The four cells of a 2 × 2 block form a cycle of length 4.
Constraints
1 <= m, n <= 500where the grid ism × n.grid[i][j]is a lowercase English letter.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| BFS with parent tracking | O(m · n) | O(m · n) |
| Optimal (union-find on grid edges) | O(m · n · α(m · n)) | O(m · n) |
1BFS with parent tracking
O(m · n)Each cell is enqueued once and checks 4 neighbours.O(m · n)Visited flags, parent indices and the queue.Run a BFS from every unvisited cell over same-letter neighbours, remembering for each cell the cell it was reached from. If a neighbour with the same letter is already visited and is not the parent, the graph has a cycle. Because grid cells have no self-loops or double edges, any such cycle has length at least 4.
- For each unvisited cell, mark it visited, set its parent to none and enqueue it.
- Pop a cell; for each of its 4 neighbours with the same letter: skip the parent.
- If the neighbour is already visited, return true; otherwise mark it, record its parent and enqueue it.
- Return false after all cells are processed.
class Solution {
public boolean containsCycle(char[][] grid) {
int m = grid.length, n = grid[0].length;
boolean[] seen = new boolean[m * n];
int[] parent = new int[m * n];
int[] dr = { 1, -1, 0, 0 }, dc = { 0, 0, 1, -1 };
ArrayDeque<Integer> q = new ArrayDeque<>();
for (int s = 0; s < m * n; s++) {
if (seen[s]) continue;
seen[s] = true;
parent[s] = -1;
q.add(s);
while (!q.isEmpty()) {
int cur = q.poll(), r = cur / n, c = cur % n;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] != grid[r][c]) continue;
int nxt = nr * n + nc;
if (nxt == parent[cur]) continue;
if (seen[nxt]) return true;
seen[nxt] = true;
parent[nxt] = cur;
q.add(nxt);
}
}
}
return false;
}
}class Solution:
def containsCycle(self, grid: List[List[str]]) -> bool:
m, n = len(grid), len(grid[0])
seen = [False] * (m * n)
parent = [-1] * (m * n)
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
for s in range(m * n):
if seen[s]:
continue
seen[s] = True
parent[s] = -1
q = deque([s])
while q:
cur = q.popleft()
r, c = divmod(cur, n)
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if nr < 0 or nc < 0 or nr >= m or nc >= n or grid[nr][nc] != grid[r][c]:
continue
nxt = nr * n + nc
if nxt == parent[cur]:
continue
if seen[nxt]:
return True
seen[nxt] = True
parent[nxt] = cur
q.append(nxt)
return Falseclass Solution {
public:
bool containsCycle(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<bool> seen(m * n, false);
vector<int> parent(m * n, -1);
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
queue<int> q;
for (int s = 0; s < m * n; s++) {
if (seen[s]) continue;
seen[s] = true;
parent[s] = -1;
q.push(s);
while (!q.empty()) {
int cur = q.front(); q.pop();
int r = cur / n, c = cur % n;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] != grid[r][c]) continue;
int nxt = nr * n + nc;
if (nxt == parent[cur]) continue;
if (seen[nxt]) return true;
seen[nxt] = true;
parent[nxt] = cur;
q.push(nxt);
}
}
}
return false;
}
};function containsCycle(grid) {
const m = grid.length, n = grid[0].length;
const seen = new Uint8Array(m * n);
const parent = new Int32Array(m * n).fill(-1);
const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
const q = new Int32Array(m * n);
for (let s = 0; s < m * n; s++) {
if (seen[s]) continue;
seen[s] = 1;
parent[s] = -1;
let head = 0, tail = 0;
q[tail++] = s;
while (head < tail) {
const cur = q[head++], r = Math.floor(cur / n), c = cur % n;
for (let d = 0; d < 4; d++) {
const nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] !== grid[r][c]) continue;
const nxt = nr * n + nc;
if (nxt === parent[cur]) continue;
if (seen[nxt]) return true;
seen[nxt] = 1;
parent[nxt] = cur;
q[tail++] = nxt;
}
}
}
return false;
}2Optimal (union-find on grid edges)
O(m · n · α(m · n))At most 2mn union/find calls, each almost constant with path compression and union by size.O(m · n)Parent and size arrays for every cell; no recursion or queue.Every pair of adjacent equal-letter cells is an edge of an undirected graph. Add the edges one by one with union-find, looking only right and down so each edge is seen once. If an edge joins two cells that are already in the same set, a path between them already exists, so this edge closes a cycle.
- Make each cell its own set (index r * n + c).
- For each cell, for its right and its lower neighbour with the same letter: find both roots.
- Equal roots → return true. Otherwise union the two sets (by size, with path compression).
- Return false.
class Solution {
private int[] parent, size;
public boolean containsCycle(char[][] grid) {
int m = grid.length, n = grid[0].length;
parent = new int[m * n];
size = new int[m * n];
for (int i = 0; i < m * n; i++) {
parent[i] = i;
size[i] = 1;
}
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (c + 1 < n && grid[r][c + 1] == grid[r][c] && !union(r * n + c, r * n + c + 1)) return true;
if (r + 1 < m && grid[r + 1][c] == grid[r][c] && !union(r * n + c, (r + 1) * n + c)) return true;
}
return false;
}
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
private boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (size[ra] < size[rb]) {
int t = ra;
ra = rb;
rb = t;
}
parent[rb] = ra;
size[ra] += size[rb];
return true;
}
}class Solution:
def containsCycle(self, grid: List[List[str]]) -> bool:
m, n = len(grid), len(grid[0])
parent = list(range(m * n))
size = [1] * (m * n)
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a: int, b: int) -> bool:
ra, rb = find(a), find(b)
if ra == rb:
return False
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
return True
for r in range(m):
row = grid[r]
for c in range(n):
if c + 1 < n and row[c + 1] == row[c] and not union(r * n + c, r * n + c + 1):
return True
if r + 1 < m and grid[r + 1][c] == row[c] and not union(r * n + c, (r + 1) * n + c):
return True
return Falseclass Solution {
public:
bool containsCycle(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
parent.resize(m * n);
sz.assign(m * n, 1);
for (int i = 0; i < m * n; i++) parent[i] = i;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++) {
if (c + 1 < n && grid[r][c + 1] == grid[r][c] && !unite(r * n + c, r * n + c + 1)) return true;
if (r + 1 < m && grid[r + 1][c] == grid[r][c] && !unite(r * n + c, (r + 1) * n + c)) return true;
}
return false;
}
private:
vector<int> parent, sz;
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
bool unite(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false;
if (sz[ra] < sz[rb]) swap(ra, rb);
parent[rb] = ra;
sz[ra] += sz[rb];
return true;
}
};function containsCycle(grid) {
const m = grid.length, n = grid[0].length;
const parent = new Int32Array(m * n), size = new Int32Array(m * n).fill(1);
for (let i = 0; i < m * n; i++) parent[i] = i;
const find = (x) => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
const union = (a, b) => {
let ra = find(a), rb = find(b);
if (ra === rb) return false;
if (size[ra] < size[rb]) [ra, rb] = [rb, ra];
parent[rb] = ra;
size[ra] += size[rb];
return true;
};
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++) {
if (c + 1 < n && grid[r][c + 1] === grid[r][c] && !union(r * n + c, r * n + c + 1)) return true;
if (r + 1 < m && grid[r + 1][c] === grid[r][c] && !union(r * n + c, (r + 1) * n + c)) return true;
}
return false;
}Edge cases to test
- A single row or column (no cycle is possible)
- A 2 × 2 block of equal letters (the shortest cycle)
- A long snake-shaped path that never closes
- A large grid of one letter (deep searches overflow a recursive DFS)
Hints
Hint 1
Treat each cell as a node, joined to its up/down/left/right neighbours that hold the same letter. You are looking for a cycle in an undirected graph.
Hint 2
During a traversal, reaching an already-visited same-letter cell that is not the cell you just came from means there is a cycle.
Hint 3
Alternatively, union each cell with its right and lower same-letter neighbours. Joining two cells that are already connected closes a cycle.
FAQ
What is the best time complexity for Detect Cycles in 2D Grid?
Optimal (union-find on grid edges) runs in O(m · n · α(m · n)) time and O(m · n) extra space. At most 2mn union/find calls, each almost constant with path compression and union by size.
Which pattern does Detect Cycles in 2D Grid use?
It is a graphs problem that uses the cycle detection pattern. Other problems with the same pattern: Undirected Graph Cycle, Directed Graph Cycle, Is Graph Bipartite?.
Is there a brute force solution for Detect Cycles in 2D Grid?
Yes. BFS with parent tracking takes O(m · n) time and O(m · n) space. Run a BFS from every unvisited cell over same-letter neighbours, remembering for each cell the cell it was reached from.
Which edge cases should I test for Detect Cycles in 2D Grid?
A single row or column (no cycle is possible); A 2 × 2 block of equal letters (the shortest cycle); A long snake-shaped path that never closes; A large grid of one letter (deep searches overflow a recursive DFS).