Skip to main content
Talentd

Parallel Courses II - Solution & Explanation

HardDynamic ProgrammingBit ManipulationGraphBitmask10 min readAsked at: Amazon, Snowflake, Google
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. 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 <= 15
  • 1 <= k <= n
  • 0 <= relations.length <= n * (n-1) / 2
  • relations[i].length == 2
  • 1 <= prevCoursei, nextCoursei <= n
  • prevCoursei != nextCoursei
  • All the pairs [prevCoursei, nextCoursei] are unique.
  • The given graph is a directed acyclic graph.

Approach Overview

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.

Approach 1: Bitmask Dynamic Programming

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Topological Sort with BFS

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Topological Sort with BFS StatesO(2^n * n)O(2^n)Good for understanding semester-by-semester progression using graph traversal
Bitmask Dynamic ProgrammingO(2^n * n)O(2^n)Optimal approach when n ≤ 15; clean state compression and efficient prerequisite checks

Video Solution

Parallel Courses II | Solution Explained in Detail • Tanishq Chaudhary • 7,295 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Parallel Courses II easy or hard?
Parallel Courses II is a Hard-level problem. The difficulty comes from combining graph prerequisites with state compression using bitmasks, which requires understanding both dynamic programming and subset enumeration.
How to solve Parallel Courses II in O(2^n * n)?
Use state compression with bitmask dynamic programming. Represent completed courses as a bitmask, compute which courses are available by checking prerequisite masks, and transition by taking subsets of up to k courses per semester. Memoization or DP ensures each state is processed once.
What is the best approach for Parallel Courses II?
The most efficient approach is Bitmask Dynamic Programming. Each DP state represents a set of completed courses using a bitmask, and transitions simulate taking up to k new courses in the next semester. This reduces the search space to at most 2^n states and allows fast prerequisite checks using bit operations.
What data structure is used in Parallel Courses II?
The solution relies on graphs for prerequisite relationships and bitmasks to represent sets of completed courses. Dynamic programming tables or BFS queues are used to explore states, while bit manipulation enables constant-time subset checks.
What is the time complexity of Parallel Courses II?
The optimal solution runs in O(2^n * n) time with O(2^n) space. Since n ≤ 15, the total number of states is manageable. Each state computes available courses and generates subsets of size up to k.
Parallel Courses II Python or Java solution approach?
Python and C++ implementations typically use Bitmask Dynamic Programming because bit operations and subset iteration are concise. Java and JavaScript solutions often implement BFS with topological constraints and state masks to simulate semester progression.
Is Parallel Courses II asked at Google, Amazon, or Meta?
Parallel Courses II is considered a high-difficulty graph and dynamic programming problem and is similar to questions asked in interviews at companies like Google, Amazon, and Meta. It tests state compression, prerequisite graph reasoning, and bitmask optimization.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Parallel Courses