Parallel Courses - Solution & Explanation

Problem Overview: You are given n courses labeled from 1 to n and a list of prerequisite relations. Each relation [a, b] means course a must be completed before b. In one semester you can take any number of courses as long as their prerequisites are satisfied. The task is to compute the minimum number of semesters required to complete all courses, or return -1 if a cycle makes it impossible.

Approach 1: Topological Sorting with Kahn's Algorithm (BFS) (Time: O(V+E), Space: O(V+E))

This problem maps directly to a directed graph where courses are nodes and prerequisites are edges. Build an adjacency list and an in-degree array that tracks how many prerequisites each course has. Start by pushing all courses with in-degree = 0 into a queue. These are the courses you can take in the first semester. Process the queue level by level using BFS; each level represents one semester.

For every course taken in the current semester, iterate through its neighbors and decrement their in-degree. When a neighbor’s in-degree becomes zero, it means all prerequisites are done and the course becomes available next semester. Count how many BFS layers you process. If the total processed courses equals n, the layer count is the answer. If some nodes remain unprocessed, the graph contains a cycle and completing all courses is impossible.

This approach works because topological sort guarantees prerequisites are handled before dependent nodes. BFS layering naturally models semesters since multiple independent courses can be taken simultaneously. The algorithm runs in linear time with respect to nodes and edges, making it optimal for large prerequisite graphs.

Approach 2: DFS + Longest Path in DAG (Time: O(V+E), Space: O(V+E))

Another way to think about the problem is computing the longest prerequisite chain. In a directed acyclic graph, the minimum semesters required equals the length of the longest path. Use graph DFS with memoization: recursively compute the depth of each node as 1 + max(depth of its neighbors). Track node states (unvisited, visiting, visited) to detect cycles during recursion.

If DFS encounters a node already marked visiting, a cycle exists and the answer is -1. Otherwise store computed depths to avoid recomputation. The final answer is the maximum depth across all courses. This approach also runs in linear time but uses recursion and explicit cycle detection rather than BFS layering.

Recommended for interviews: The BFS topological sort using Kahn's algorithm is the most expected solution. It clearly models semesters as graph layers and handles cycle detection naturally by counting processed nodes. DFS with longest-path logic demonstrates deeper graph understanding, but BFS topological sort is usually the quickest and most readable solution during interviews.