Parallel Courses

Explanation & Solution

Description

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] = [prevCourse_i, nextCourse_i] means that course prevCourse_i must be taken before course nextCourse_i (a prerequisite relationship).

In one semester, you can take any number of courses as long as all prerequisites for each course have been completed in a previous semester.

Return the minimum number of semesters needed to take all courses. If there is no way to take all courses (due to a cycle in prerequisites), return -1.

Input: n = 3, relations = [[1,3],[2,3]]

Output: 2

Explanation: In the first semester, courses 1 and 2 can be taken (no prerequisites). In the second semester, course 3 can be taken since both its prerequisites are complete.

Constraints

1 <= n <= 5000
1 <= relations.length <= 5000
relations[i].length == 2
1 <= prevCourse_i, nextCourse_i <= n
prevCourse_i != nextCourse_i
All pairs [prevCourse_i, nextCourse_i] are unique

Approach

Topological Sort pattern

1. Build the Directed Graph

Create an adjacency list for courses 1 to n.
For each relation [prev, next], add a directed edge from prev to next.
Track each node's in-degree (number of prerequisites).

2. Initialize with Zero In-Degree Courses

Courses with in-degree 0 have no prerequisites and can be taken immediately.
Add all such courses to the BFS queue. These form the first semester.

3. BFS Level-by-Level (Semester by Semester)

Process all courses in the current queue as one semester (one BFS level).
For each completed course, decrement the in-degree of its dependent courses.
If a dependent course's in-degree reaches 0, it is now unlocked and added to the queue for the next semester.
Increment the semester counter after processing each level.

4. Track Completed Courses

Count every course that is dequeued and processed.
After BFS finishes, if the completed count equals n, all courses were taken successfully.

5. Detect Cycles and Return Result

If completed < n, some courses are stuck in a cycle (their in-degree never reached 0). Return -1.
Otherwise, return the number of semesters.

Key Insight

This is a BFS-based topological sort where each BFS level represents one semester. The number of levels gives the minimum semesters because each level processes all courses whose prerequisites are met in parallel.

Time

O(n + e) where e is the number of relations.

Space

O(n + e) for the graph and in-degree array.

Solution Code

Find All Possible Recipes from Given Supplies

Minimum Height Trees