DSA problem
Parallel Courses
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, nextCourse], representing a prerequisite relationship between course prevCourse and course nextCourse: course prevCourse has to be taken before course nextCourse.
In one semester, you can take any number of courses as long as you have taken all the prerequisites in the previous semesters 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.
This is the classic "shortest schedule" version of topological sort. Each semester corresponds to one BFS layer of Kahn's algorithm: every course whose prerequisites are already satisfied (in-degree zero) can be taken simultaneously. After processing that layer, we decrement the in-degree of each successor; any successor that hits zero becomes available for the next semester.
The algorithm bookkeeping is straightforward. Build the adjacency list and an in-degree array. Push every course with in-degree zero into a queue, then repeatedly pop the entire current queue as one semester, enqueueing every successor whose in-degree drops to zero. The answer is the number of layers processed — provided every course was visited. If any course is left unvisited at the end, the graph has a cycle and we return -1. The whole thing runs in O(n + e) time and O(n + e) space.
Examples
n = 3, relations = [[1,3],[2,3]]2n = 3, relations = [[1,2],[2,3],[3,1]]-1n = 5, relations = [[1,2],[1,3],[3,4],[3,5]]3Constraints
- 1 <= n <= 5000
- 1 <= relations.length <= 5000
- relations[i].length == 2
- 1 <= prevCourse, nextCourse <= n
- prevCourse != nextCourse
- All the pairs [prevCourse, nextCourse] are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.