How do you solve Shortest Cycle in a Graph on LeetCode?

Shortest Cycle in a Graph (LeetCode #2608) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n + e) time complexity and O(n) space complexity. Key insight: BFS is effective for finding shortest paths in unweighted graphs.

What is the brute force solution for Shortest Cycle in a Graph?

The brute force approach for Shortest Cycle in a Graph is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves checking all possible paths from each vertex to find cycles. This is straightforward but inefficient, as it may explore many unnecessary paths. The optimal Optimal Solution approach improves this to O(n + e).

What algorithm or data structure is used to solve Shortest Cycle in a Graph?

Shortest Cycle in a Graph uses the following concepts: Breadth-First Search, Graph Theory. The recommended patterns to study are: Graph Traversal, Breadth-First Search, Cycle Detection.

What are the interview tips for Shortest Cycle in a Graph?

Explain your thought process clearly while coding. Discuss edge cases, like disconnected graphs or single edges. Practice BFS and DFS separately to solidify understanding.

What are common mistakes when solving Shortest Cycle in a Graph?

Not handling the parent node correctly in cycle detection. Confusing distance tracking with visited tracking.

#2608

Shortest Cycle in a Graph

Hard

Breadth-First SearchGraph TheoryGraph TraversalBreadth-First SearchCycle Detection

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n + e)
Space	O(n)	O(n)

💡

Intuition

Time O(n + e)Space O(n)

Using Breadth-First Search (BFS) allows us to explore the graph level by level, ensuring that we find the shortest cycle efficiently by keeping track of distances from the starting node.

⚙️

Algorithm

5 steps

1Step 1: Construct the graph using an adjacency list.
2Step 2: For each vertex, perform BFS to find the shortest cycle that includes that vertex.
3Step 3: Maintain a distance array to track the distance of each node from the starting node.
4Step 4: If a neighbor is found that has already been visited and is not the parent, calculate the cycle length.
5Step 5: Update the minimum cycle length found.

solution.py25 lines

1# Full working Python code
2from collections import deque, defaultdict
3
4def shortest_cycle(n, edges):
5    graph = defaultdict(list)
6    for u, v in edges:
7        graph[u].append(v)
8        graph[v].append(u)
9
10    min_cycle_length = float('inf')
11
12    for start in range(n):
13        queue = deque([start])
14        distance = {start: 0}
15        while queue:
16            node = queue.popleft()
17            for neighbor in graph[node]:
18                if neighbor not in distance:
19                    distance[neighbor] = distance[node] + 1
20                    queue.append(neighbor)
21                elif distance[neighbor] >= distance[node]:
22                    cycle_length = distance[node] + distance[neighbor] + 1
23                    min_cycle_length = min(min_cycle_length, cycle_length)
24
25    return min_cycle_length if min_cycle_length != float('inf') else -1

ℹ

Complexity note: The time complexity is O(n + e) where e is the number of edges, as we explore each vertex and its edges. The space complexity is O(n) for the distance map.

1BFS is effective for finding shortest paths in unweighted graphs.
2Cycles can be detected by revisiting nodes in BFS with distance tracking.

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