⚡Flashcard Drill➔
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

  1. DFS over cells of equal value, tracking the parent cell.
  2. If a neighbour has already been visited and is not the parent, we have found a back edge -- a cycle.
  3. The parent check is what prevents treating the edge back to the previous cell as a cycle.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems