Parallel Courses II - Practice Coding Problems

Parallel Courses II - 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] = [prevCourse_i, nextCourse_i], representing a prerequisite relationship between course prevCourse_i and course nextCourse_i: course prevCourse_i has to be taken before course nextCourse_i.

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.

Input & Output

Example 1 — Basic Prerequisites

$ Input: n = 4, relations = [[2,1],[3,1],[1,4]], k = 2

› Output: 3

💡 Note: Course 1 needs courses 2 and 3. Course 4 needs course 1. Semester 1: take 2,3. Semester 2: take 1. Semester 3: take 4.

Example 2 — No Prerequisites

$ Input: n = 3, relations = [], k = 2

› Output: 2

💡 Note: No prerequisites, so we can take any courses. Take 2 courses per semester: Semester 1: courses 1,2. Semester 2: course 3.

Example 3 — Linear Chain

$ Input: n = 3, relations = [[1,2],[2,3]], k = 1

› Output: 3

💡 Note: Linear dependency: 1→2→3. Must take one course per semester in order: 1, then 2, then 3.

Constraints

1 ≤ n ≤ 15
1 ≤ k ≤ n
0 ≤ relations.length ≤ n × (n-1) / 2
relations[i].length == 2
1 ≤ prevCourse_i, nextCourse_i ≤ n
prevCourse_i ≠ nextCourse_i
All the pairs [prevCourse_i, nextCourse_i] are unique
The given graph is a valid DAG (directed acyclic graph)

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

4 courses with prerequisites: 2,3→1→4, can take 2 per semester

Dependency Resolution

Build prerequisite graph and find valid course combinations

Optimal Schedule

Minimum 3 semesters: {2,3} → {1} → {4}

Key Takeaway

🎯 Key Insight: Use bitmask DP to efficiently track course completion states and find optimal semester scheduling

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use bitmask dynamic programming where each bit represents course completion status. Build prerequisite relationships as bitmasks, then use DP to find minimum transitions. Best approach uses dp[mask] to store minimum semesters needed from state mask. Time: O(3ⁿ), Space: O(2ⁿ).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Schedules	O(2ⁿ × n!)	O(n)	Generate all possible ways to schedule courses and find minimum semesters
Dynamic Programming with Bitmask	O(3ⁿ × k)	O(2ⁿ)	Use bitmask DP to efficiently track course completion states

Brute Force - Try All Schedules — Algorithm Steps

Step 1: Generate all possible subsets of courses for each semester
Step 2: Check if prerequisites are satisfied for each subset
Step 3: Recursively try remaining courses in next semester
Step 4: Return minimum semesters across all valid schedules

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Combinations

Create all possible course combinations for each semester

Check Prerequisites

Verify each combination satisfies prerequisite constraints

Find Minimum

Return the schedule with minimum semesters

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int n, k;
int prereq[15][15];
int prereq_count[15];

int backtrack(int taken_mask, int semester) {
    int taken_count = __builtin_popcount(taken_mask);
    if (taken_count == n) return semester;
    
    int available[15];
    int available_count = 0;
    
    for (int course = 1; course <= n; course++) {
        if (!(taken_mask & (1 << course))) {
            int can_take = 1;
            for (int j = 0; j < prereq_count[course]; j++) {
                int pre = prereq[course][j];
                if (!(taken_mask & (1 << pre))) {
                    can_take = 0;
                    break;
                }
            }
            if (can_take) {
                available[available_count++] = course;
            }
        }
    }
    
    if (available_count == 0) return INT_MAX;
    
    int min_semesters = INT_MAX;
    int max_take = (available_count < k) ? available_count : k;
    
    for (int mask = 1; mask < (1 << available_count); mask++) {
        if (__builtin_popcount(mask) > max_take) continue;
        
        int new_taken = taken_mask;
        for (int i = 0; i < available_count; i++) {
            if (mask & (1 << i)) {
                new_taken |= (1 << available[i]);
            }
        }
        
        int result = backtrack(new_taken, semester + 1);
        if (result < min_semesters) {
            min_semesters = result;
        }
    }
    
    return min_semesters;
}

int solution(int n_param, int relations[][2], int relations_size, int k_param) {
    n = n_param;
    k = k_param;
    
    memset(prereq_count, 0, sizeof(prereq_count));
    
    for (int i = 0; i < relations_size; i++) {
        int prev = relations[i][0];
        int next = relations[i][1];
        prereq[next][prereq_count[next]++] = prev;
    }
    
    return backtrack(0, 0);
}

int main() {
    int n, k;
    scanf("%d", &n);
    
    // Skip relations parsing for simplicity in this brute force approach
    int relations[20][2];
    int relations_size = 0;
    
    scanf("%d", &k);
    
    int result = solution(n, relations, relations_size, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n!)

Each course can be taken in any semester, leading to exponential combinations

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth and course tracking arrays

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Schedules — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler