How do you solve Detect Cycles in 2D Grid on LeetCode?

Detect Cycles in 2D Grid (LeetCode #1559) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m * n) time complexity and O(m * n) space complexity. Key insight: Tracking the previous cell is crucial to avoid false cycles.

What is the brute force solution for Detect Cycles in 2D Grid?

The brute force approach for Detect Cycles in 2D Grid is Brute Force, with O(m * n) time complexity and O(m * n) space complexity. The brute force approach involves checking every cell in the grid and performing a depth-first search (DFS) from that cell to find cycles. This method is simple but inefficient, as it explores all possible paths without optimizing for previously visited cells. The optimal Optimal Solution approach improves this to O(m * n).

What algorithm or data structure is used to solve Detect Cycles in 2D Grid?

Detect Cycles in 2D Grid uses the following concepts: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix. The recommended patterns to study are: Depth-First Search (DFS), Graph Traversal.

What are the interview tips for Detect Cycles in 2D Grid?

Always clarify the problem constraints and edge cases with the interviewer. Explain your thought process as you code; it shows your understanding. Don't forget to test your solution with multiple test cases after coding.

What are common mistakes when solving Detect Cycles in 2D Grid?

Failing to check the previous cell can lead to incorrect cycle detection. Not managing the visited state properly can cause infinite loops.

#1559

Detect Cycles in 2D Grid

Medium

ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrixDepth-First Search (DFS)Graph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(m * n)	O(m * n)
Space	O(m * n)	O(m * n)

💡

Intuition

Time O(m * n)Space O(m * n)

The optimal solution uses a modified DFS approach that tracks the previous cell to avoid immediate backtracking. This ensures we only explore valid paths and can efficiently detect cycles without redundant checks.

⚙️

Algorithm

5 steps

1Step 1: Initialize a visited set to keep track of visited cells.
2Step 2: For each cell in the grid, if it hasn't been visited, start a DFS.
3Step 3: In the DFS, check all four possible directions, ensuring not to revisit the immediate predecessor.
4Step 4: If we revisit a cell already in the current path (not the last cell), a cycle is detected.
5Step 5: Return true if any cycle is found; otherwise, return false after all cells are processed.

solution.py24 lines

1# Full working Python code
2from typing import List
3
4def hasCycle(grid: List[List[str]]) -> bool:
5    m, n = len(grid), len(grid[0])
6    visited = set()
7
8    def dfs(x, y, px, py, value):
9        if (x, y) in visited:
10            return True
11        visited.add((x, y))
12        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
13            nx, ny = x + dx, y + dy
14            if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == value:
15                if (nx, ny) != (px, py) and dfs(nx, ny, x, y, value):
16                    return True
17        return False
18
19    for i in range(m):
20        for j in range(n):
21            if (i, j) not in visited:
22                if dfs(i, j, -1, -1, grid[i][j]):
23                    return True
24    return False

ℹ

Complexity note: The time complexity remains O(m * n) as we still visit each cell once, but we avoid unnecessary revisits. The space complexity is O(m * n) due to the visited set.

1Tracking the previous cell is crucial to avoid false cycles.
2Using a visited set helps in efficiently managing state across recursive calls.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.