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. Also, you are given the integer k.
In one semester, you can take at most k 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. The testcases will be generated such that it is possible to take every course.
Example 1:
Input: n = 4, relations = [[2,1],[3,1],[1,4]], k = 2 Output: 3 Explanation: The figure above represents the given graph. In the first semester, you can take courses 2 and 3. In the second semester, you can take course 1. In the third semester, you can take course 4.
Example 2:
Input: n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2 Output: 4 Explanation: The figure above represents the given graph. In the first semester, you can only take courses 2 and 3 since you cannot take more than two per semester. In the second semester, you can take course 4. In the third semester, you can take course 1. In the fourth semester, you can take course 5.
Constraints:
1 <= n <= 151 <= k <= n0 <= relations.length <= n * (n-1) / 2relations[i].length == 21 <= prevCoursei, nextCoursei <= nprevCoursei != nextCoursei[prevCoursei, nextCoursei] are unique.Problem Overview: You are given n courses with prerequisite relations and can take at most k courses per semester. The goal is to compute the minimum number of semesters required to complete all courses while respecting the prerequisite graph.
The challenge is that multiple courses can be taken simultaneously, but only if their prerequisites are already completed. With n ≤ 15, the search space is manageable using bitmasks to represent which courses have already been completed.
Approach 1: Topological Sort with BFS State Exploration (≈O(2^n * n) time, O(2^n) space)
Model the problem as a graph where edges represent prerequisite dependencies. Instead of processing a single order like standard topological sort, each BFS state represents a bitmask of completed courses. For the current mask, compute which courses are available by checking prerequisites using bit operations. If the number of available courses is ≤ k, take all of them. Otherwise generate combinations of size k and push new states into the BFS queue.
This effectively performs a level-by-level search where each level corresponds to a semester. A visited set prevents revisiting the same mask. The approach works well for small n but becomes expensive because generating combinations for each state may expand the search significantly.
Approach 2: Bitmask Dynamic Programming (O(2^n * n) time, O(2^n) space)
This approach treats each subset of courses as a DP state. A bitmask of length n represents which courses have already been completed. Precompute prerequisite masks so that checking if a course can be taken becomes a constant-time bit operation.
For each state, compute the set of courses whose prerequisites are satisfied and are not yet taken. From that set, generate all subsets of size ≤ k. Each subset represents courses you take in the next semester. Transition to the new mask using mask | subset and update the DP value as dp[newMask] = min(dp[newMask], dp[mask] + 1).
The key optimization comes from representing courses using bit manipulation and iterating through subsets efficiently. Since n ≤ 15, the total number of masks is at most 2^15, which makes this dynamic programming approach feasible.
Recommended for interviews: The Dynamic Programming solution using a bitmask is the standard interview answer. It demonstrates strong understanding of state compression and subset transitions. The BFS state-search approach helps build intuition by extending topological sorting, but the bitmask DP version is usually cleaner and easier to reason about in terms of complexity.
This approach uses bitmasking along with dynamic programming to efficiently represent the state of which courses have been completed. Since n is relatively small (up to 15), bitmasking can efficiently represent all possible states of course completion.
We'll define a DP state, dp[mask], where 'mask' is a bitmask representation of the courses taken so far. The value of dp[mask] will represent the minimum number of semesters needed to complete the courses represented by the mask.
Transitions occur based on selecting a valid subset of courses (up to k) that can be taken in the current semester, ensuring all prerequisites have been met.
This Python solution uses a recursive approach with memoization (via @lru_cache). Each course is associated with a prerequisite bitmask. We attempt all valid combinations of courses that can be taken simultaneously (up to k at a time) and transition between states (bitmasks) to determine the minimum number of semesters required.
Time Complexity: O(2^n * n^2), where n is the number of courses. This results from the state space determined by 2^n possible states and iterating over available courses (n^2 due to combinations).
Space Complexity: O(2^n), arising from the memoization storage.
The second approach involves performing a topological sort using a Breadth-First Search (BFS) which processes nodes (courses) by taking prerequisites into account. Each node can be processed only once all its prerequisites are processed. This forms the basis of obtaining the order of completion for the courses.
By performing a topological sort, we appropriately order the courses, allowing for maximizing the number of courses taken per semester (up to k).
This Java solution implements BFS for topological sorting. It uses an indegree array to track prerequisites and processes nodes with no remaining prerequisites. The BFS collects the maximum number of nodes (courses) available per semester, ensures optimal course selection, and counts required semesters.
Java
JavaScript
Time Complexity: O(n + m), where n is the number of courses and m is the number of prerequisites (edges in the graph). Each node and edge is processed once.
Space Complexity: O(n + m), holding the graph structure and BFS queue.
| Approach | Complexity |
|---|---|
| Bitmask Dynamic Programming | Time Complexity: O(2^n * n^2), where n is the number of courses. This results from the state space determined by 2^n possible states and iterating over available courses (n^2 due to combinations). Space Complexity: O(2^n), arising from the memoization storage. |
| Topological Sort with BFS | Time Complexity: O(n + m), where n is the number of courses and m is the number of prerequisites (edges in the graph). Each node and edge is processed once. Space Complexity: O(n + m), holding the graph structure and BFS queue. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Topological Sort with BFS States | O(2^n * n) | O(2^n) | Good for understanding semester-by-semester progression using graph traversal |
| Bitmask Dynamic Programming | O(2^n * n) | O(2^n) | Optimal approach when n ≤ 15; clean state compression and efficient prerequisite checks |
Parallel Courses II | Solution Explained in Detail • Tanishq Chaudhary • 6,888 views views
Watch 9 more video solutions →Practice Parallel Courses II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor