NeetCode #598LC-2101MediumGraphs
← Back to All Problems#598 · #2101 · Detonate the Maximum Bombs(引爆最多的炸弹)
📌 Problem Statement & Constraints
Given an
m x n grid of characters, return whether there is a cycle of length 4 or more: four or more cells of the same value connected 4-directionally in a loop. Constraints: 1 <= m, n <= 500, grid[i][j] is a lowercase letter.💡 Core Algorithmic Approaches
- DFS over cells of equal value, tracking the parent cell.
- If a neighbour has already been visited and is not the parent, we have found a back edge -- a cycle.
- The parent check is what prevents treating the edge back to the previous cell as a cycle.
- Each cell is visited once, so the whole thing is O(m*n).
💻 Benchmark Python3 Implementation
class Solution:
def containsCycle(self, grid: List[List[str]]) -> bool:
m, n = len(grid), len(grid[0])
seen = [[False] * n for _ in range(m)]
def dfs(r: int, c: int, pr: int, pc: int) -> bool:
seen[r][c] = True
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if not (0 <= nr < m and 0 <= nc < n) or grid[nr][nc] != grid[r][c]:
continue
if not seen[nr][nc]:
if dfs(nr, nc, r, c):
return True
elif (nr, nc) != (pr, pc):
return True # visited and not the parent -> cycle
return False
for i in range(m):
for j in range(n):
if not seen[i][j] and dfs(i, j, -1, -1):
return True
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n): each cell is visited once.
💾 Space Complexity
O(m * n) for the visited array plus the recursion depth.
⚠️ Interview Pitfalls & Follow-ups
- Omitting the parent check: every edge would look like a cycle.
- Tracking only the parent's value: the parent must be identified by coordinates.
- Requiring the cycle length to be exactly 4: the minimum is 4, but longer cycles count too.
- Recursing on a 500x500 grid: the depth can reach 250 000; an iterative DFS with an explicit stack is safer.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.