Detect Cycles in 2D Grid — Solution in Python, Java & C++
Detect Cycles in 2D Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Detect Cycles in 2D Grid is a medium coding problem on arrays, depth-first search and matrix, asked in Amazon, Google and Nutanix interviews.
- Difficulty: Medium
- Topics: Arrays, Depth-First Search, Matrix, Breadth-First Search, Union Find
- Asked at: Amazon, Google, Nutanix
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a grid of lowercase letters, one string per row. A cycle is a path of length 4 or more that starts and ends on the same cell, moves only between side-adjacent cells holding the same letter, and never steps straight back to the cell it just came from.
Return true if the grid contains any cycle.
Example 1
Input: grid = ["aaaa","abca","aada","aaaa"]
Output: true
Example 2
Input: grid = ["aaaa","abca","aaaa"]
Output: true
Example 3
Input: grid = ["ab","ba"]
Output: false
Constraints
1 <= grid.length <= 12All rows have the same length, between 1 and 12.The grid contains only lowercase English letters.
Hints for Detect Cycles in 2D Grid
Hint 1
Explore each same-letter region with a DFS, carrying the cell you arrived from.
Hint 2
Skip that parent cell so a simple back-and-forth is not mistaken for a cycle.
Hint 3
Reaching an already-visited cell that is not the parent means a cycle exists.
How to solve Detect Cycles in 2D Grid
DFS each same-letter region carrying the parent cell; reaching an already-visited cell that is not the parent means a cycle.
Approach
- For each unvisited cell, DFS with
(cell, parent). - For each same-letter neighbour other than the parent: return
trueif visited, else mark and push. - Return
false.
Why it works
In an undirected graph a DFS back edge to a non-parent visited node closes a cycle, and every grid cycle has length ≥ 4 automatically since the grid is bipartite.
Complexity
- Time —
O(m · n) - Space —
O(m · n)
Pitfalls
- Skipping the parent is what prevents a single edge from being seen as a cycle.
Reference solution
Python
def containsCycle(grid) -> bool:
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if seen[r][c]:
continue
letter = grid[r][c]
stack = [(r, c, -1, -1)]
seen[r][c] = True
while stack:
cr, cc, pr, pc = stack.pop()
for nr, nc in ((cr + 1, cc), (cr - 1, cc), (cr, cc + 1), (cr, cc - 1)):
if not (0 <= nr < rows and 0 <= nc < cols):
continue
if grid[nr][nc] != letter or (nr == pr and nc == pc):
continue
if seen[nr][nc]:
return True
seen[nr][nc] = True
stack.append((nr, nc, cr, cc))
return FalseJava
public static boolean containsCycle(String[] grid) {
int rows = grid.length, cols = grid[0].length();
boolean[][] seen = new boolean[rows][cols];
int[] dr = {1, -1, 0, 0};
int[] dc = {0, 0, 1, -1};
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (seen[r][c]) continue;
char letter = grid[r].charAt(c);
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{r, c, -1, -1});
seen[r][c] = true;
while (!stack.isEmpty()) {
int[] cell = stack.pop();
for (int d = 0; d < 4; d++) {
int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
if (grid[nr].charAt(nc) != letter) continue;
if (nr == cell[2] && nc == cell[3]) continue;
if (seen[nr][nc]) return true;
seen[nr][nc] = true;
stack.push(new int[]{nr, nc, cell[0], cell[1]});
}
}
}
}
return false;
}C++
bool containsCycle(vector<string>& grid) {
int rows = (int) grid.size(), cols = (int) grid[0].size();
vector<vector<bool>> seen(rows, vector<bool>(cols, false));
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (seen[r][c]) continue;
char letter = grid[r][c];
vector<array<int,4>> stack;
stack.push_back({r, c, -1, -1});
seen[r][c] = true;
while (!stack.empty()) {
array<int,4> cell = stack.back();
stack.pop_back();
for (int d = 0; d < 4; d++) {
int nr = cell[0] + dr[d], nc = cell[1] + dc[d];
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
if (grid[nr][nc] != letter) continue;
if (nr == cell[2] && nc == cell[3]) continue;
if (seen[nr][nc]) return true;
seen[nr][nc] = true;
stack.push_back({nr, nc, cell[0], cell[1]});
}
}
}
}
return false;
}JavaScript
var containsCycle = function(grid) {
const rows = grid.length, cols = grid[0].length;
const seen = [];
for (let r = 0; r < rows; r++) {
const row = [];
for (let c = 0; c < cols; c++) row.push(false);
seen.push(row);
}
const dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (seen[r][c]) continue;
const letter = grid[r].charAt(c);
const stack = [[r, c, -1, -1]];
seen[r][c] = true;
while (stack.length > 0) {
const cell = stack.pop();
for (let d = 0; d < 4; d++) {
const nr = cell[0] + dr[d], nc = cell[1] + dc[d];
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
if (grid[nr].charAt(nc) !== letter) continue;
if (nr === cell[2] && nc === cell[3]) continue;
if (seen[nr][nc]) return true;
seen[nr][nc] = true;
stack.push([nr, nc, cell[0], cell[1]]);
}
}
}
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Depth-First Search (DFS)