# Parallel Courses II
**Difficulty:** HARD
[External](https://leetcode.com/problems/parallel-courses-ii)
Canonical: https://scaleengineer.com/dsa/problems/parallel-courses-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/parallel-courses-ii/image0.png) 

**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:**

![](https://assets.glich.co/dsa/parallel-courses-ii/image1.png) 

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

# Approaches
## State-Space Search with BFS
This approach models the problem as a shortest path problem on a state-space graph. Each state is represented by a bitmask, where the i-th bit is set if course `i` has been completed. We use Breadth-First Search (BFS) to explore the states, semester by semester, guaranteeing that we find the path with the minimum number of steps (semesters).
**Time:** O(2^n * C(n, k) * n). For each of the `2^n` states, we might need to generate up to `C(n, k)` next states, where `C(n, k)` is the number of combinations. Generating each next state and available courses takes O(n) time. This is too slow for the given constraints if `k` is close to `n/2`. · **Space:** O(2^n) to store the distance to each state (mask) and for the queue used in BFS.
**Pros:** Guaranteed to find the optimal solution.; Conceptually straightforward as it directly maps to a shortest path problem on a graph.
**Cons:** The time complexity is very high, making it infeasible for larger values of `n`.; Generating all combinations of courses to take at each step can be complex to implement and computationally expensive.; The performance is heavily dependent on `k`, being particularly slow when `k` is close to `n/2`.
### Explanation
The core idea is to perform a BFS over the `2^n` possible states (subsets of courses). We start from the state `0` (no courses taken) and aim to reach the state `(1 << n) - 1` (all courses taken).

- **State Representation**: A bitmask `mask` of length `n` represents the set of courses taken.
- **Prerequisites**: We first precompute a `prereq` array where `prereq[i]` is a bitmask representing all direct prerequisites for course `i`.
- **BFS Execution**:
  - A queue stores the masks to visit, and a `dist` array tracks the minimum semesters to reach each mask.
  - We start with `dist[0] = 0` and `queue.offer(0)`.
  - When we process a `mask`, we first identify all courses that can be taken in the next semester. A course is available if it hasn't been taken yet and all its prerequisites are in `mask`.
  - From the set of available courses, we must choose a subset of size at most `k`. To ensure optimality, we should always take as many courses as possible, which is `min(k, number_of_available_courses)`. 
  - We then generate all combinations of this size from the available courses. Each combination leads to a new state (next mask). If a new state is visited for the first time, we update its distance and add it to the queue.
- The search ends when we dequeue the final mask `(1 << n) - 1`, and `dist[final_mask]` gives the answer.

```java
import java.util.*;

class Solution {
    public int minNumberOfSemesters(int n, int[][] relations, int k) {
        int[] prereq = new int[n];
        for (int[] rel : relations) {
            // Courses are 1-indexed in input, convert to 0-indexed
            prereq[rel[1] - 1] |= 1 << (rel[0] - 1);
        }

        int[] dist = new int[1 << n];
        Arrays.fill(dist, -1);
        Queue<Integer> queue = new LinkedList<>();

        dist[0] = 0;
        queue.offer(0);

        while (!queue.isEmpty()) {
            int mask = queue.poll();
            if (mask == (1 << n) - 1) {
                return dist[mask];
            }

            int availableCoursesMask = 0;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0) { // if course i is not taken
                    if ((mask & prereq[i]) == prereq[i]) { // and prereqs are met
                        availableCoursesMask |= (1 << i);
                    }
                }
            }

            int numAvailable = Integer.bitCount(availableCoursesMask);
            int numToTake = Math.min(k, numAvailable);

            if (numAvailable <= k) {
                int nextMask = mask | availableCoursesMask;
                if (dist[nextMask] == -1) {
                    dist[nextMask] = dist[mask] + 1;
                    queue.offer(nextMask);
                }
            } else {
                // Iterate through all submasks of availableCoursesMask with k bits
                for (int submask = availableCoursesMask; submask > 0; submask = (submask - 1) & availableCoursesMask) {
                    if (Integer.bitCount(submask) == numToTake) {
                        int nextMask = mask | submask;
                        if (dist[nextMask] == -1) {
                            dist[nextMask] = dist[mask] + 1;
                            queue.offer(nextMask);
                        }
                    }
                }
            }
        }
        return -1; // Should not be reached as a solution is guaranteed
    }
}
```
### Algorithm
- Represent the set of completed courses using a bitmask. Each bitmask is a state in a state-space graph.
- The problem becomes finding the shortest path from state `0` (no courses taken) to state `(1 << n) - 1` (all courses taken).
- Use Breadth-First Search (BFS) to find the shortest path, as each transition (taking courses for one semester) has a weight of 1.
- Start a queue with the initial state `0` and maintain a `dist` array to store the minimum semesters to reach each state.
- In each step of the BFS, for a given state `mask`:
  1. Determine the set of `available_courses` whose prerequisites are all satisfied within `mask`.
  2. It is always optimal to take as many courses as possible. So, we decide to take `m = min(k, |available_courses|)` courses.
  3. Generate all combinations of `m` courses from the `available_courses` set.
  4. Each combination forms a new state `next_mask`. If `next_mask` has not been visited, update its distance and add it to the queue.
- The BFS terminates when the final state is reached, and its distance is the minimum number of semesters.

## Dynamic Programming with Bitmasking
A more efficient approach is to use dynamic programming on subsets of courses. We define a `dp` state `dp[mask]` as the minimum number of semesters required to finish the courses represented by the bitmask `mask`. We build up the solution by iterating through all possible subsets of courses and considering what could have been taken in the last semester to reach the current state.
**Time:** O(3^n * n). The outer loop runs `2^n` times for `mask`. The inner loop iterates through all submasks of `mask`. The total number of pairs `(mask, submask)` is `3^n`. Inside the loop, calculating prerequisites for the submask takes O(n). This is efficient enough for `n <= 15`. · **Space:** O(2^n) for the `dp` array that stores the results for all `2^n` subsets of courses.
**Pros:** Guaranteed to find the optimal solution.; Generally more efficient than the BFS approach, with a time complexity that does not depend on `k`.; It's a standard technique for problems involving optimal solutions on subsets.
**Cons:** The exponential time complexity limits its applicability to small `n`.; The concept of DP on subsets and iterating through submasks can be non-trivial to grasp and implement correctly.
### Explanation
This method systematically computes the minimum semesters for every subset of courses, from smaller subsets to larger ones.

- **State Definition**: `dp[mask]` = minimum number of semesters to complete the courses in the subset represented by `mask`.
- **Initialization**: We initialize a `dp` array of size `2^n` with a large value (e.g., `n+1`) and set `dp[0] = 0`.
- **Prerequisites**: As before, we precompute `prereq[i]` for each course `i`, which is a bitmask of its prerequisites.
- **Transitions**: We iterate `mask` from 1 to `(1 << n) - 1`. To calculate `dp[mask]`, we look backward. We consider all possible subsets of courses (`submask`) that could have been taken in the final semester to achieve the state `mask`. The state before that would be `prev_mask = mask ^ submask`.
  - We iterate through all `submask`s of `mask`.
  - For each `submask`, we check two conditions:
    1. `Integer.bitCount(submask) <= k`: The number of courses taken in the semester does not exceed `k`.
    2. All prerequisites for courses in `submask` are satisfied by `prev_mask`. We can check this by ensuring the bitmask of all prerequisites for `submask` is a sub-mask of `prev_mask`.
  - If both conditions are met, we have a valid transition, and we update `dp[mask] = Math.min(dp[mask], dp[prev_mask] + 1)`.
- The final result is the value of `dp[(1 << n) - 1]`.

The total number of pairs `(mask, submask)` across the loops is `3^n`, leading to the overall time complexity.

```java
import java.util.Arrays;

class Solution {
    public int minNumberOfSemesters(int n, int[][] relations, int k) {
        // prereq[i] is a bitmask of prerequisites for course i
        int[] prereq = new int[n];
        for (int[] rel : relations) {
            // Courses are 1-indexed in input, convert to 0-indexed
            prereq[rel[1] - 1] |= (1 << (rel[0] - 1));
        }

        // dp[mask] is the minimum semesters to complete courses in mask
        int[] dp = new int[1 << n];
        Arrays.fill(dp, n + 1); // Initialize with a value larger than any possible answer
        dp[0] = 0;

        for (int mask = 1; mask < (1 << n); mask++) {
            // Iterate over all submasks of mask. `submask` represents the courses taken in the last semester.
            for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                if (Integer.bitCount(submask) > k) {
                    continue;
                }

                int prevMask = mask ^ submask;
                
                // Check if submask is a valid set of courses to take after prevMask is completed.
                int prereqsForSubmask = 0;
                for (int i = 0; i < n; i++) {
                    if (((submask >> i) & 1) == 1) { // if course i is in submask
                        prereqsForSubmask |= prereq[i];
                    }
                }

                // All prerequisites for submask must be satisfied by prevMask
                if ((prereqsForSubmask & prevMask) == prereqsForSubmask) {
                    dp[mask] = Math.min(dp[mask], dp[prevMask] + 1);
                }
            }
        }

        return dp[(1 << n) - 1];
    }
}
```
### Algorithm
- Use dynamic programming with bitmasking, where `dp[mask]` stores the minimum number of semesters to complete the courses represented by `mask`.
- The base case is `dp[0] = 0` (0 semesters for 0 courses).
- Iterate through each `mask` from 1 to `(1 << n) - 1` to compute `dp[mask]`.
- To compute `dp[mask]`, we consider the last semester. The courses taken in this last semester form a subset of `mask`, let's call it `submask`.
- The state before the last semester was `prev_mask = mask ^ submask`.
- For a `submask` to be a valid choice for a single semester:
  1. The number of courses in it must not exceed `k`.
  2. All prerequisites for courses in `submask` must have been completed in `prev_mask`.
- We iterate through all possible `submask`s of the current `mask`. If a `submask` is a valid last-semester choice, we can update the `dp` value: `dp[mask] = min(dp[mask], dp[prev_mask] + 1)`.
- The final answer is `dp[(1 << n) - 1]`.

# Solutions
### Java

```java
class Solution {
public
  int minNumberOfSemesters(int n, int[][] relations, int k) {
    int[] d = new int[n + 1];
    for (var e : relations) {
      d[e[1]] |= 1 << e[0];
    }
    Deque<int[]> q = new ArrayDeque<>();
    q.offer(new int[]{0, 0});
    Set<Integer> vis = new HashSet<>();
    vis.add(0);
    while (!q.isEmpty()) {
      var p = q.pollFirst();
      int cur = p[0], t = p[1];
      if (cur == (1 << (n + 1)) - 2) {
        return t;
      }
      int nxt = 0;
      for (int i = 1; i <= n; ++i) {
        if ((cur & d[i]) == d[i]) {
          nxt |= 1 << i;
        }
      }
      nxt ^= cur;
      if (Integer.bitCount(nxt) <= k) {
        if (vis.add(nxt | cur)) {
          q.offer(new int[]{nxt | cur, t + 1});
        }
      } else {
        int x = nxt;
        while (nxt > 0) {
          if (Integer.bitCount(nxt) == k && vis.add(nxt | cur)) {
            q.offer(new int[]{nxt | cur, t + 1});
          }
          nxt = (nxt - 1) & x;
        }
      }
    }
    return 0;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minNumberOfSemesters(int n, vector<vector<int>> &relations, int k) {
    vector<int> d(n + 1);
    for (auto &e : relations) {
      d[e[1]] |= 1 << e[0];
    }
    queue<pair<int, int>> q;
    q.push({0, 0});
    unordered_set<int> vis{{0}};
    while (!q.empty()) {
      auto [cur, t] = q.front();
      q.pop();
      if (cur == (1 << (n + 1)) - 2) {
        return t;
      }
      int nxt = 0;
      for (int i = 1; i <= n; ++i) {
        if ((cur & d[i]) == d[i]) {
          nxt |= 1 << i;
        }
      }
      nxt ^= cur;
      if (__builtin_popcount(nxt) <= k) {
        if (!vis.count(nxt | cur)) {
          vis.insert(nxt | cur);
          q.push({nxt | cur, t + 1});
        }
      } else {
        int x = nxt;
        while (nxt) {
          if (__builtin_popcount(nxt) == k && !vis.count(nxt | cur)) {
            vis.insert(nxt | cur);
            q.push({nxt | cur, t + 1});
          }
          nxt = (nxt - 1) & x;
        }
      }
    }
    return 0;
  }
};

```

### Python

```python
class Solution:
    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int: d = [0] * (n + 1) for x, y in relations: d[y] |= 1 << x q = deque([(0, 0)]) vis = {0} while q: cur, t = q . popleft() if cur == (1 << (n + 1)) - 2: return t nxt = 0 for i in range(1, n + 1): if (cur & d[i]) == d[i]: nxt |= 1 << i nxt ^= cur if nxt . bit_count() <= k: if (nxt | cur) not in vis: vis . add(nxt | cur) q . append((nxt | cur, t + 1)) else: x = nxt while nxt: if nxt . bit_count() == k and (nxt | cur) not in vis: vis . add(nxt | cur) q . append((nxt | cur, t + 1)) nxt = (nxt - 1) & x

```