🌱 Keegan's Digital Garden

1494. Parallel Courses II

4 min read

📝 Problem Details

💭What Were My Initial Thoughts?

- explicitly construct a graph via an adjacency list since the number of possible nodes is small (1 - 15)
- also create a separate structure to store the degree weights for edges

- when solving the problem by hand, we look at how many relationships a given node has pointing to it, we can
compare that number with k using the modulo operator and get the remainder, this could be done recursively as there could be multiple semesters needed to be added before that unit is able to be compelted.

🤔What Did I Struggle With?

- missing application of dp and bitmasking to this problem

💡 Explanation of Solution

Bitmasking and DP

Why Bitmasking?

  • Compact State Representation:
    • Each course can either be completed (1) or not (0). Using a bitmask, the ith bit represents whether course i is completed.
    • For n courses, the state space is 2^n (all possible subsets of courses), which is feasible since 1 <= n <= 15.
  • Efficient Operations:
    • Prerequisite checks, state transitions, and subset generation can be handled using efficient bitwise operations.

Why DP?

  • The problem requires minimizing the number of semesters, which can be solved by breaking it into subproblems:
    • Let dp[mask] represent the minimum semesters required to complete the courses encoded by mask.
    • Start with dp[0] = 0 (no courses completed, 0 semesters required) and iteratively build up to dp[(1 << n) - 1] (all courses completed).

Steps to Solve Using DP with Bitmasking

  1. Prerequisite Representation:

    • Convert the prerequisites into bitmasks for each course. For a course i, the prerequisite bitmask prereq[i] indicates which courses need to be completed before i can be taken.

  2. Define the DP State:

    • dp[mask] represents the minimum semesters required to complete the courses encoded by mask.

  3. State Transitions:

    • For each mask (current state of completed courses), calculate:
      • Available Courses: Courses that can be taken next based on prerequisites.
      • Subsets of Available Courses: Generate all valid subsets of the available courses that can be taken in one semester (up to k courses).

  4. DP Update:

    • For each subset of courses taken in the current semester, compute the new state and update the DP table: 
      dp[newMask] = min(dp[newMask], dp[mask] + 1);
      where newMask = mask | subset.

  5. Final Result:

    • The final answer is dp[(1 << n) - 1], representing the minimum semesters to complete all courses.

Key Observations

  • Using subsets allows handling the constraint of taking at most k courses per semester.
  • Bitwise operations enable fast checking of prerequisites and transitions.

⌛ Complexity Analysis

Time Complexity:

  1. State Space:
    • There are 2^n possible states (mask).
  2. Subset Iteration:
    • For each state, subsets of available courses are generated. The total number of subsets over all states is (3^n) (since each course can be included, excluded, or unavailable in a given state).
  3. Prerequisite Checks:
    • Checking prerequisites for all courses is (O(n)) per state.

Thus, the overall time complexity is: [O(3^n \cdot n)]

Space Complexity:

  • The DP table requires (O(2^n)) space.
  • Additional space for prereq and intermediate variables is (O(n)).

Total Space Complexity: (O(2^n + n)).

💻 Implementation of Solution

class Solution {
public:
    int minNumberOfSemesters(int n, vector<vector<int>>& prerequisites, int k) {
        // Step 1: Build the graph and prerequisite masks
        vector<int> prereq(n, 0); // prerequisite bitmask for each course
        for (auto& pre : prerequisites) {
            int u = pre[0] - 1; // 0-indexed
            int v = pre[1] - 1; // 0-indexed
            prereq[v] |= (1 << u); // Add `u` as a prerequisite for `v`
        }
 
        // Step 2: Dynamic Programming
        int fullMask = (1 << n) - 1; // All courses taken
        vector<int> dp(1 << n, INT_MAX); // dp[mask]: min semesters to complete courses in `mask`
        dp[0] = 0; // No courses taken -> 0 semesters
 
        for (int mask = 0; mask <= fullMask; ++mask) {
            if (dp[mask] == INT_MAX) continue;
 
            // Find courses that can be taken next (prerequisites satisfied)
            int available = 0;
            for (int i = 0; i < n; ++i) {
                if ((mask & prereq[i]) == prereq[i] && !(mask & (1 << i))) {
                    available |= (1 << i);
                }
            }
 
            // Iterate over subsets of `available` (courses to take this semester)
            for (int subset = available; subset > 0; subset = (subset - 1) & available) {
                if (__builtin_popcount(subset) > k) continue; // Limit to `k` courses per semester
                dp[mask | subset] = min(dp[mask | subset], dp[mask] + 1);
            }
        }
 
        return dp[fullMask];
    }
};

Graph View