Problem Description

You are given a 2D grid of characters with dimensions m x n. Your task is to determine if there exists a cycle in the grid where all cells in the cycle contain the same character value.

A cycle is defined as a path that:

• Has a length of 4 or more cells
• Starts and ends at the same cell
• Each move goes from the current cell to an adjacent cell (up, down, left, or right)
• All cells in the path must have the same character value
• You cannot immediately return to the cell you just came from (no immediate backtracking)

For example, if you move from cell (1, 1) to cell (1, 2), you cannot immediately move back to (1, 1) in the next step - this would be an invalid cycle.

The function should return true if at least one valid cycle exists anywhere in the grid, and false otherwise.

The solution uses BFS (Breadth-First Search) to explore the grid. For each unvisited cell, it starts a BFS traversal while keeping track of:

• The parent cell (previous position) to avoid immediate backtracking
• Visited cells to detect when we encounter a cell we've seen before
• When we find a cell with the same value that has already been visited (and isn't the parent), we've found a cycle

The algorithm systematically checks all possible starting positions and paths to ensure no cycles are missed.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The 2D grid can be viewed as a graph where each cell is a node, and edges connect adjacent cells with the same character value.

Is it a tree?

• No: The problem specifically asks about finding cycles, which means the graph structure can have cycles (trees by definition don't have cycles).

Is the problem related to directed acyclic graphs?

• No: The problem is about finding cycles in an undirected graph (cells connect bidirectionally to their neighbors).

Is the problem related to shortest paths?

• No: We're not looking for shortest paths; we're looking for the existence of cycles.

Does the problem involve connectivity?

• Yes: The problem involves connectivity - we need to check if cells with the same value can form a connected cycle.

Does the problem have small constraints?

• Yes: While the grid can be up to a certain size, we're exploring locally connected components which typically have manageable constraints for DFS/backtracking.

DFS/backtracking?

• Yes: DFS is perfect for cycle detection as we need to explore paths and track visited nodes to detect when we return to a previously visited cell.

Conclusion: The flowchart suggests using DFS/backtracking for detecting cycles in the 2D grid. DFS allows us to explore paths while maintaining the parent information to avoid immediate backtracking, and tracking visited cells to detect when we complete a cycle.

Intuition

When we think about finding cycles in a 2D grid, we need to understand what makes a valid cycle. A cycle means we can start from a cell and return to it by following a path of cells with the same value, without immediately backtracking.

The key insight is that cycle detection in graphs is a classic application of DFS or BFS. When we traverse the graph and encounter a cell we've already visited (that isn't our immediate parent), we've found a cycle.

Why does this work? Consider how we explore the grid:

1. We start from an unvisited cell and mark it as visited
2. We explore its neighbors that have the same character value
3. For each neighbor, we continue exploring recursively
4. If during exploration we reach a cell that's already been visited AND it's not the cell we just came from, we've completed a cycle

The critical part is tracking the parent cell (where we came from). Without this, we might incorrectly identify going back and forth between two cells as a cycle. For example, moving from (1,1) → (1,2) → (1,1) is not a valid cycle because it's just backtracking.

We need to check every unvisited cell as a potential starting point because cycles might exist in disconnected components of the grid. Each component with the same character value needs to be explored separately.

The algorithm naturally handles the "length 4 or more" requirement because:

• We can't immediately go back (parent check)
• To return to the starting cell, we must go through at least 2 other cells
• This gives us: start → cell1 → cell2 → start (minimum 4 cells including return)

Whether we use DFS or BFS doesn't fundamentally change the approach - both can detect cycles by tracking visited cells and parent relationships. The solution uses BFS with a queue, but DFS with recursion would work equally well.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The solution implements a BFS approach to detect cycles in the 2D grid. Let's walk through the implementation step by step:

1. Initialize the Grid Traversal:

m, n = len(grid), len(grid[0])
vis = [[False] * n for _ in range(m)]
dirs = (-1, 0, 1, 0, -1)

• Create a vis matrix to track visited cells
• Define dirs for the four directions (up, right, down, left) using a clever pairwise technique

2. Iterate Through All Cells:

for i, row in enumerate(grid):
    for j, x in enumerate(row):
        if vis[i][j]:
            continue

• Check each cell as a potential starting point for a new component
• Skip already visited cells since they've been explored in previous BFS traversals

3. BFS Implementation:

vis[i][j] = True
q = [(i, j, -1, -1)]

• Mark the starting cell as visited
• Initialize queue with (current_x, current_y, parent_x, parent_y)
• Parent coordinates are set to (-1, -1) for the starting cell

4. Process the Queue:

while q:
    x, y, px, py = q.pop()
    for dx, dy in pairwise(dirs):
        nx, ny = x + dx, y + dy

• Pop from the queue (using it as a stack for DFS-like behavior)
• Generate next coordinates using pairwise(dirs) which creates pairs like (-1, 0), (0, 1), (1, 0), (0, -1)

5. Validate and Process Neighbors:

if 0 <= nx < m and 0 <= ny < n:
    if grid[nx][ny] != grid[i][j] or (nx == px and ny == py):
        continue
    if vis[nx][ny]:
        return True
    vis[nx][ny] = True
    q.append((nx, ny, x, y))

• Check if the next cell is within bounds
• Skip if it has a different value or if it's the parent cell (avoiding immediate backtracking)
• Critical cycle detection: If we encounter a visited cell that's not our parent and has the same value, we've found a cycle
• Otherwise, mark the cell as visited and add it to the queue with current cell as parent

6. Return Result:

• If we complete all BFS traversals without finding a cycle, return False

The algorithm ensures that each connected component of same-valued cells is explored exactly once. The parent tracking mechanism prevents false cycle detection from immediate backtracking, while the visited matrix helps identify true cycles when we re-encounter a previously visited cell through a different path.

Example Walkthrough

Let's walk through a small example to illustrate how the BFS solution detects cycles.

Consider this 3x3 grid:

a a b
a a b
b b b

Step 1: Start at (0,0) with value 'a'

• Mark (0,0) as visited
• Queue: [(0,0, parent:(-1,-1))]
• Visited: {(0,0)}

Step 2: Process (0,0)

• Check neighbors with value 'a':
  • Right (0,1): Same value 'a', not visited → Add to queue
  • Down (1,0): Same value 'a', not visited → Add to queue
• Mark both as visited
• Queue: [(0,1, parent:(0,0)), (1,0, parent:(0,0))]
• Visited: {(0,0), (0,1), (1,0)}

Step 3: Process (1,0)

• Check neighbors with value 'a':
  • Up (0,0): Same value 'a', but it's the parent → Skip
  • Right (1,1): Same value 'a', not visited → Add to queue
• Mark (1,1) as visited
• Queue: [(0,1, parent:(0,0)), (1,1, parent:(1,0))]
• Visited: {(0,0), (0,1), (1,0), (1,1)}

Step 4: Process (1,1)

• Check neighbors with value 'a':
  • Up (0,1): Same value 'a', already visited, NOT the parent → CYCLE FOUND!

The cycle is: (0,0) → (0,1) → (1,1) → (1,0) → (0,0)

This forms a valid cycle because:

• All cells have the same value 'a'
• The path has 4 cells
• We never immediately backtrack (parent check prevents this)
• We return to a previously visited cell through a different path

The algorithm returns true immediately upon detecting this cycle.

Key observations:

• The parent tracking prevented us from incorrectly identifying (1,0) → (0,0) → (1,0) as a cycle
• The visited set helped us detect when we reached (0,1) from a different path
• Each 'a' cell was explored exactly once as part of this connected component

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n) where m is the number of rows and n is the number of columns in the grid.

Each cell in the grid is visited at most once due to the vis array tracking visited cells. When we encounter an already visited cell from the outer loops, we skip it with continue. During the BFS/DFS traversal (using a stack here), each cell is processed once when it's marked as visited. Although we check up to 4 neighbors for each cell, this is a constant factor. Therefore, the overall time complexity is O(m × n).

Space Complexity: O(m × n) where m is the number of rows and n is the number of columns in the grid.

The space is used for:

1. The vis array which stores boolean values for all m × n cells: O(m × n)
2. The queue/stack q which in the worst case (like a spiral pattern) could contain up to O(m × n) elements
3. The dirs tuple and other variables use O(1) space

The dominant factor is the vis array and potentially the queue, both of which are O(m × n), resulting in an overall space complexity of O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Parent Tracking Leading to False Positives

One of the most common mistakes is not properly tracking the parent cell, which can lead to incorrectly identifying a cycle when you simply encounter the cell you just came from.

Incorrect Implementation:

# Wrong: Not tracking parent properly
stack = [(start_row, start_col)]  # Missing parent information

while stack:
    curr_row, curr_col = stack.pop()
  
    for delta_row, delta_col in directions:
        next_row, next_col = curr_row + delta_row, curr_col + delta_col
      
        if 0 <= next_row < rows and 0 <= next_col < cols:
            if grid[next_row][next_col] == grid[start_row][start_col]:
                if visited[next_row][next_col]:  # This will trigger falsely!
                    return True

Why it fails: Without parent tracking, when you move from cell A to cell B, and then explore B's neighbors, you'll immediately encounter A again as visited, incorrectly detecting a "cycle" of length 2.

Correct Solution: Always maintain parent coordinates and skip the parent cell during neighbor exploration:

stack = [(start_row, start_col, -1, -1)]  # Include parent coords

while stack:
    curr_row, curr_col, parent_row, parent_col = stack.pop()
  
    for delta_row, delta_col in directions:
        next_row, next_col = curr_row + delta_row, curr_col + delta_col
      
        # Skip if it's the parent cell
        if next_row == parent_row and next_col == parent_col:
            continue

2. Using Global Visited Matrix Incorrectly

Another pitfall is using a single global visited matrix without resetting it for each connected component, or conversely, resetting it unnecessarily.

Incorrect Implementation:

# Wrong: Resetting visited for each starting cell
for start_row in range(rows):
    for start_col in range(cols):
        visited = [[False] * cols for _ in range(rows)]  # Reset everything!
        visited[start_row][start_col] = True
        # ... rest of BFS/DFS

Why it fails: This prevents you from skipping already-explored cells, leading to redundant work and potentially incorrect cycle detection across component boundaries.

Correct Solution: Use a single visited matrix throughout and only process unvisited cells:

visited = [[False] * cols for _ in range(rows)]  # Initialize once

for start_row in range(rows):
    for start_col in range(cols):
        if visited[start_row][start_col]:  # Skip already visited
            continue
        # Process this component

3. Mixing BFS Queue with DFS Stack Behavior

The code uses q.pop() which actually implements DFS (stack behavior) despite the variable being named q (suggesting queue). While both work for cycle detection, mixing concepts can cause confusion.

Potentially Confusing:

q = [(i, j, -1, -1)]  # Named like a queue
while q:
    x, y, px, py = q.pop()  # But used as a stack (DFS)

Clearer Implementation: Choose one approach consistently:

# For DFS (using stack):
stack = [(i, j, -1, -1)]
while stack:
    x, y, px, py = stack.pop()
  
# For BFS (using deque):
from collections import deque
queue = deque([(i, j, -1, -1)])
while queue:
    x, y, px, py = queue.popleft()

Both approaches work for cycle detection, but being consistent with naming and behavior improves code readability and reduces confusion during debugging.