Skip to main content
Talentd

Parallel Courses - Solution & Explanation

MediumPremiumFree on FleetCodeGraphTopological Sort10 min readAsked at: Amazon, Meta, Netflix +4
Practice this problem

Problem Statement

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given an array relations where relations[i] = [prevCoursei, nextCoursei], representing a prerequisite relationship between course prevCoursei and course nextCoursei: course prevCoursei has to be taken before course nextCoursei.

In one semester, you can take any number of courses as long as you have taken all the prerequisites in the previous semester for the courses you are taking.

Return the minimum number of semesters needed to take all courses. If there is no way to take all the courses, return -1.

 

Example 1:

Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: The figure above represents the given graph.
In the first semester, you can take courses 1 and 2.
In the second semester, you can take course 3.

Example 2:

Input: n = 3, relations = [[1,2],[2,3],[3,1]]
Output: -1
Explanation: No course can be studied because they are prerequisites of each other.

 

Constraints:

  • 1 <= n <= 5000
  • 1 <= relations.length <= 5000
  • relations[i].length == 2
  • 1 <= prevCoursei, nextCoursei <= n
  • prevCoursei != nextCoursei
  • All the pairs [prevCoursei, nextCoursei] are unique.

Approach Overview

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.

Solution

We can first build a graph g to represent the prerequisite relationships between courses, and count the in-degree indeg of each course.

Then we enqueue the courses with an in-degree of 0 and start topological sorting. Each time, we dequeue a course from the queue, reduce the in-degree of the courses that it points to by 1, and if the in-degree becomes 0 after reduction, we enqueue that course. When the queue is empty, if there are still courses that have not been completed, it means that it is impossible to complete all courses, so we return -1. Otherwise, we return the number of semesters required to complete all courses.

The time complexity is O(n + m), and the space complexity is O(n + m). Here, n and m are the number of courses and the number of prerequisite relationships, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Topological Sort (Kahn's Algorithm BFS)O(V+E)O(V+E)Best general solution. Models semesters as BFS levels and handles cycle detection cleanly.
DFS with Longest Path in DAGO(V+E)O(V+E)Useful when solving DAG depth problems or when DFS with memoization fits the graph workflow.

Video Solution

PARALLEL COURSES | LEETCODE 1136 | PYTHON TOPOLOGICAL SORT • Cracking FAANG • 4,323 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Parallel Courses easy or hard?
Parallel Courses is generally considered a medium-level graph problem. The main challenge is recognizing that the course dependency structure forms a directed graph and that topological sorting can determine a valid processing order and detect cycles.
Parallel Courses Python/Java solution
Most implementations follow the same structure across languages: build the adjacency list, compute in-degrees, push zero in-degree nodes into a queue, and run BFS. Python commonly uses collections.deque, while Java implementations use Queue and ArrayList for adjacency storage.
How to solve Parallel Courses in O(V+E)?
Construct a directed graph from prerequisite relations and compute the in-degree of every course. Push all nodes with in-degree 0 into a queue and perform BFS. For each processed course, decrement the in-degree of its neighbors and add newly unlocked courses to the queue. Counting BFS levels gives the minimum number of semesters.
What is the best approach for Parallel Courses?
Topological sorting using Kahn's algorithm (BFS) is the most practical approach. Build an adjacency list and track in-degrees for each course, then process nodes with zero prerequisites level by level. Each BFS layer represents one semester. The algorithm runs in O(V+E) time and naturally detects cycles.
Is Parallel Courses asked at Google/Amazon/Meta?
Graph scheduling problems using topological sort frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include course scheduling, dependency resolution, and build order problems. Parallel Courses specifically tests understanding of DAG traversal and BFS-based topological sorting.
What data structure is used in Parallel Courses?
The solution typically uses an adjacency list to represent the directed graph, an array to track in-degrees, and a queue for BFS processing. These structures allow efficient updates when prerequisites are satisfied and enable level-by-level traversal for semester counting.
What is the time complexity of Parallel Courses?
The optimal solution runs in O(V+E) time where V is the number of courses and E is the number of prerequisite relations. Building the graph takes O(E) and the topological traversal processes each node and edge once. Space complexity is also O(V+E) for the adjacency list and in-degree array.

Ready to solve this problem?

Practice Parallel Courses with our built-in code editor and test cases.

Practice on FleetCode
Previous

Course Schedule II

Next

Parallel Courses II