Detect Cycles in 2D Grid

Detect Cycles in 2D Grid

What is this problem about?

The Detect Cycles in 2D Grid coding problem asks you to find if there exists a cycle of length 4 or more in a 2D grid of characters. A cycle is defined as a path of the same character that starts and ends at the same cell, where each step moves to an adjacent cell (up, down, left, or right) and no cell is visited twice except for the starting cell.

Why is this asked in interviews?

Meta and Amazon ask this to test your proficiency with graph interview patterns applied to a grid. It evaluations your ability to adapt standard algorithms like DFS or Union Find to a 2D space. It also checks if you can handle the "parent" constraint (not moving back to the cell you just came from), which is the most critical part of cycle detection.

Algorithmic pattern used

The most common approach is Depth-First Search (DFS).

1. Iterate through each unvisited cell in the grid.
2. Start a DFS from that cell, keeping track of the character being matched.
3. In the DFS, pass the current coordinates and the "parent" coordinates (where you came from).
4. If you encounter a cell that is already visited and is not the parent, a cycle exists.

Example explanation

Grid:

a a a
a b a
a a a

The 'a's form a square around the 'b'.

1. Start DFS at (0,0) for character 'a'.
2. Move to (0,1), then (0,2), then (1,2), then (2,2), then (2,1), then (2,0), then (1,0).
3. From (1,0), you look at (0,0). (0,0) is visited and is NOT the parent of (1,0). Result: true.

Common mistakes candidates make

• Hitting the Parent: Forgetting to exclude the immediate predecessor from the "visited" check, which leads to false positives (cycles of length 2).
• Resetting Visited: Not properly marking cells as visited across different starting points, leading to $O(N^2 imes M^2)$ complexity instead of $O(N imes M)$.
• Path Limitation: Failing to ensure all cells in the cycle have the same character.

Interview preparation tip

Cycle detection in grids is identical to cycle detection in undirected graphs. Remember the rule: "If you see a visited node that isn't your parent, you've found a cycle."