Parallel Courses (Minimum Semesters)

📋

Problem

Imagine you are planning your university semesters and want to finish all your courses in the minimum number of semesters possible, respecting prerequisite constraints.

You are given an integer n representing the number of courses labeled from 1 to n. You are also given an array relations where relations[i] = [prevCourse_i, nextCourse_i], representing a prerequisite relationship: course prevCourse_i must be taken before course nextCourse_i. In one semester, you can take any number of courses as long as all their prerequisites are met. Return the minimum number of semesters needed to take all courses. If it is impossible to finish all courses, return -1.

1 ≤ n ≤ 10^51 ≤ relations.length ≤ 5 * 10^5relations[i].length == 21 ≤ prevCourse_i, nextCourse_i ≤ nprevCourse_i != nextCourse_i

Edge cases: No prerequisites (relations is empty) → minimum semesters is 1Single course with no prerequisites → minimum semesters is 1Cycle in prerequisites → return -1

</>

IDE

def min_semesters(n: int, relations: list[list[int]]) -> int:public int minSemesters(int n, int[][] relations)int minSemesters(int n, vector<vector<int>>& relations)function minSemesters(n, relations)

def min_semesters(n, relations):
    # Write your solution here
    pass

class Solution {
    public int minSemesters(int n, int[][] relations) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int minSemesters(int n, vector<vector<int>>& relations) {
    // Write your solution here
    return 0;
}

function minSemesters(n, relations) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1Ignoring prerequisites and returning 1 semester regardless of input.✅ Implement BFS topological sort to process courses respecting prerequisites.

Wrong: -1Incorrectly detecting cycles when none exist.✅ Ensure cycle detection only triggers if some courses remain unprocessed after BFS.

Wrong: nGreedy approach taking one course per semester even when multiple courses can be taken in parallel.✅ Process all zero in-degree courses per BFS level to minimize semesters.

Wrong: n-1Off-by-one error in semester counting, starting count from zero instead of one.✅ Initialize semester count to zero and increment after processing each BFS level.

Wrong: TLEUsing brute force or DFS backtracking approach with exponential complexity.✅ Use BFS topological sort with in-degree arrays for O(n+m) time complexity.

✓

Test Cases

Focus on handling empty and minimal inputs correctly, and detecting cycles.

Watch out for greedy traps and off-by-one errors in semester counting.

Optimize your solution to linear time using BFS topological sort with in-degree arrays.

t1_01basic

Input{"n":3,"relations":[[1,3],[2,3]]}

Expected2

⏱ Performance - must finish in 2000ms

Courses 1 and 2 can be taken in the first semester, and course 3 in the second semester.

💡 Think about topological sorting and how to process courses level by level.

💡 Use Kahn's algorithm to track courses with zero prerequisites each semester.

💡 Count the number of BFS layers until all courses are taken or a cycle is detected.

Why it failed: Returned wrong semester count; likely missed counting parallel courses per semester or cycle detection. Fix by implementing BFS level traversal with in-degree updates.

✓ Correctly computed minimum semesters using BFS topological sort.

t1_02basic

Input{"n":4,"relations":[[1,2],[2,3],[3,4]]}

Expected4

⏱ Performance - must finish in 2000ms

Linear chain of prerequisites requires one course per semester, total 4 semesters.

💡 Consider the longest prerequisite chain as the minimum semesters needed.

💡 Kahn's algorithm BFS will process one course per semester in this chain.

💡 Ensure to increment semester count each BFS level until all courses are processed.

Why it failed: Incorrect output due to not handling linear chains properly; possibly treating all courses as parallel. Fix by counting BFS levels correctly.

✓ Correctly handled linear chain prerequisite scenario.

t2_01edge

Input{"n":5,"relations":[]}

Expected1

⏱ Performance - must finish in 2000ms

No prerequisites means all courses can be taken in one semester.

💡 If no prerequisites, all courses are available immediately.

💡 Check if in-degree array is all zeros at start.

💡 Return 1 since all courses can be taken simultaneously.

Why it failed: Returned more than 1 semester despite no prerequisites; fix by checking if all courses have zero in-degree initially.

✓ Correctly returned 1 semester for no prerequisite case.

t2_02edge

Input{"n":1,"relations":[]}

Expected1

⏱ Performance - must finish in 2000ms

Single course with no prerequisites requires only one semester.

💡 Single course with zero in-degree is available immediately.

💡 Check base case where n=1 and no relations.

💡 Return 1 as minimum semesters.

Why it failed: Returned incorrect semester count for single course; fix by handling n=1 base case correctly.

✓ Correctly handled single course no prerequisite case.

t2_03edge

Input{"n":3,"relations":[[1,2],[2,3],[3,1]]}

Expected-1

⏱ Performance - must finish in 2000ms

Cycle exists among courses 1, 2, and 3; impossible to finish all courses.

💡 Detect cycles by checking if all courses can be processed in topological order.

💡 If some courses remain with non-zero in-degree after BFS, a cycle exists.

💡 Return -1 when cycle detected.

Why it failed: Failed to detect cycle; returned positive semester count. Fix by verifying if all courses are processed after BFS.

✓ Correctly detected cycle and returned -1.

t3_01corner

Input{"n":5,"relations":[[1,3],[2,3],[3,4],[3,5]]}

Expected3

⏱ Performance - must finish in 2000ms

Courses 1 and 2 in semester 1, course 3 in semester 2, courses 4 and 5 in semester 3.

💡 Beware of greedy approaches that pick only one course per semester.

💡 Use BFS to process all available courses in parallel each semester.

💡 Count BFS levels correctly to get minimum semesters.

Why it failed: Greedy approach taking one course per semester leads to overcounting semesters. Fix by processing all zero in-degree courses per BFS level.

✓ Correctly handled parallel courses per semester.

t3_02corner

Input{"n":4,"relations":[[1,2],[1,3],[2,4],[3,4]]}

Expected3

⏱ Performance - must finish in 2000ms

Courses 1 in semester 1, courses 2 and 3 in semester 2, course 4 in semester 3.

💡 Check that you do not confuse 0/1 knapsack style single picks with parallel picks here.

💡 All courses with zero in-degree can be taken simultaneously.

💡 Use BFS level count as semester count.

Why it failed: Confused 0/1 picking with parallel picks; returned fewer semesters than possible. Fix by counting BFS levels properly.

✓ Correctly distinguished parallel course taking from single picks.

t3_03corner

Input{"n":6,"relations":[[1,4],[2,4],[3,5],[4,6],[5,6]]}

Expected3

⏱ Performance - must finish in 2000ms

Courses 1,2,3 in semester 1, courses 4 and 5 in semester 2, course 6 in semester 3.

💡 Watch for off-by-one errors in semester counting.

💡 Ensure semester count increments after processing each BFS level.

💡 Verify all courses are counted and BFS completes.

Why it failed: Off-by-one error in semester count; fix by incrementing semester count after processing each BFS level.

✓ Correctly counted semesters with no off-by-one errors.

t4_01performance

Input{"n":100,"relations":[[1,2],[2,3],[3,4],[4,5],[5,6],[6,7],[7,8],[8,9],[9,10],[10,11],[11,12],[12,13],[13,14],[14,15],[15,16],[16,17],[17,18],[18,19],[19,20],[20,21],[21,22],[22,23],[23,24],[24,25],[25,26],[26,27],[27,28],[28,29],[29,30],[30,31],[31,32],[32,33],[33,34],[34,35],[35,36],[36,37],[37,38],[38,39],[39,40],[40,41],[41,42],[42,43],[43,44],[44,45],[45,46],[46,47],[47,48],[48,49],[49,50],[50,51],[51,52],[52,53],[53,54],[54,55],[55,56],[56,57],[57,58],[58,59],[59,60],[60,61],[61,62],[62,63],[63,64],[64,65],[65,66],[66,67],[67,68],[68,69],[69,70],[70,71],[71,72],[72,73],[73,74],[74,75],[75,76],[76,77],[77,78],[78,79],[79,80],[80,81],[81,82],[82,83],[83,84],[84,85],[85,86],[86,87],[87,88],[88,89],[89,90],[90,91],[91,92],[92,93],[93,94],[94,95],[95,96],[96,97],[97,98],[98,99],[99,100]]}

Expected100

⏱ Performance - must finish in 2000ms

Linear chain of 100 courses requires 100 semesters; O(n+m) solution must complete within 2 seconds.

💡 Use Kahn's algorithm with adjacency list and in-degree array for O(n+m) complexity.

💡 Avoid backtracking or DFS with cycle detection that is exponential.

💡 Process BFS level by level to count semesters efficiently.

Why it failed: TLE due to exponential or inefficient approach; fix by implementing O(n+m) BFS topological sort.

✓ Efficient O(n+m) solution confirmed by passing performance test.

Practice

1. Consider the following Python code implementing the optimal approach to find eventual safe states. Given the input graph = [[1],[2],[3],[]], what is the final returned list of safe nodes?

from collections import deque

def eventualSafeNodes(graph):
    n = len(graph)
    reverse_graph = [[] for _ in range(n)]
    in_degree = [0] * n

    for u in range(n):
        for v in graph[u]:
            reverse_graph[v].append(u)
        in_degree[u] = len(graph[u])

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    safe = []

    while queue:
        node = queue.popleft()
        safe.append(node)
        for prev in reverse_graph[node]:
            in_degree[prev] -= 1
            if in_degree[prev] == 0:
                queue.append(prev)

    return sorted(safe)

easy

A. [3]

B. [0, 3]

C. [0, 1, 2, 3]

D. [1, 2, 3]

Solution

1. Step 1: Initialize in-degree and reverse graph

   Graph has edges: 0->1, 1->2, 2->3, 3->none. So in_degree = [1,1,1,0], reverse_graph = [[],[0],[1],[2]].

2. Step 2: Process queue starting with nodes having in-degree 0

   Start with node 3 in queue. Pop 3, safe=[3]. Decrement in_degree of 2 to 0, add 2 to queue. Pop 2, safe=[3,2]. Decrement in_degree of 1 to 0, add 1. Pop 1, safe=[3,2,1]. Decrement in_degree of 0 to 0, add 0. Pop 0, safe=[3,2,1,0].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All nodes lead to terminal node 3, so all are safe [OK]

Hint: Nodes with zero out-degree start the safe node chain [OK]

Common Mistakes:

• Forgetting to sort final safe list
• Miscounting in-degree initialization
• Off-by-one errors in queue processing

2. You are given a directed graph where each node has a color represented by a lowercase letter. The goal is to find the maximum number of occurrences of any single color along any path in the graph. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy traversal selecting the most frequent color at each step

B. Dijkstra's algorithm to find shortest paths weighted by color frequency

C. Topological sort combined with iterative dynamic programming to track color counts

D. Simple DFS exploring all paths without memoization

Solution

1. Step 1: Understand problem constraints and graph properties

   The problem requires tracking maximum color counts along paths in a directed graph, which may contain dependencies and cycles.

2. Step 2: Identify suitable algorithm

   Topological sort linearizes nodes respecting dependencies, enabling iterative DP to accumulate color counts efficiently without redundant recomputation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Topological sort + DP handles dependencies and cycles correctly [OK]

Hint: Topological sort enables DP on DAGs [OK]

Common Mistakes:

• Assuming greedy or simple DFS suffices without cycle detection

3. Examine the following code snippet for the largest color value problem. It is almost correct but contains one subtle bug. Identify the line causing the bug.

from collections import defaultdict, deque

def largestPathValue(colors, edges):
    n = len(colors)
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    dp = [[0]*26 for _ in range(n)]
    queue = deque([i for i in range(n) if indegree[i] == 0])
    count = 0
    max_color_value = 0

    while queue:
        node = queue.popleft()
        count += 1
        c_index = ord(colors[node]) - ord('a')
        dp[node][c_index] += 1
        max_color_value = max(max_color_value, dp[node][c_index])

        for nei in graph[node]:
            for i in range(26):
                dp[nei][i] = max(dp[nei][i], dp[node][i])
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)

    if count != n:
        return -1  # cycle detected
    return max_color_value

medium

A. Line incrementing dp[node][c_index]

B. Line updating dp[nei][i] inside the nested loop

C. Line checking if count != n to detect cycles

D. Line initializing the queue with nodes having indegree zero

Solution

1. Step 1: Understand dp update logic

   dp[nei][i] should aggregate max counts from predecessors, but the code overwrites dp[nei][i] without adding the neighbor's own color count.

2. Step 2: Identify bug

   The bug is that dp[nei][i] = max(dp[nei][i], dp[node][i]) does not add the neighbor's own color count, causing undercounting.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Incorrect aggregation leads to wrong max color values [OK]

Hint: Check if dp updates correctly accumulate color counts [OK]

Common Mistakes:

• Not aggregating color counts from neighbors properly

4. Suppose the problem is modified so that nodes can be revisited multiple times (cycles allowed). Which modification to the iterative DFS approach is necessary to correctly find all paths from source to target without infinite loops?

hard

A. Add a visited set per path to prevent revisiting nodes already in the current path

B. Remove path tracking and rely on global visited set to avoid cycles

C. Use BFS instead of DFS to guarantee shortest paths and avoid cycles

D. No modification needed; the current approach handles cycles correctly

Solution

1. Step 1: Identify cycle problem

   Allowing revisits means cycles can cause infinite loops if not tracked per path.

2. Step 2: Solution approach

   Maintain a visited set per path to avoid revisiting nodes already in the current path, preventing cycles.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Global visited set disallows legitimate different paths; per-path visited set is needed [OK]

Hint: Cycle detection requires per-path visited tracking, not global visited [OK]

Common Mistakes:

• Using global visited set incorrectly
• Assuming no cycles without checks

5. Suppose the course prerequisites can form multiple disconnected subgraphs and some courses have no prerequisites. How should Kahn's Algorithm be modified to return a valid order including all courses?

hard

A. Initialize the queue with all nodes having zero in-degree, including those in disconnected components.

B. Use backtracking to try all permutations since BFS cannot handle disconnected graphs.

C. Run DFS from each node separately and concatenate results without cycle checks.

D. Start BFS from any arbitrary node and ignore disconnected components.

Solution

1. Step 1: Identify disconnected components

   Courses with no prerequisites form disconnected subgraphs with zero in-degree nodes.

2. Step 2: Initialize queue with all zero in-degree nodes

   Queue must include all such nodes to process all components and produce a full valid order.

3. Step 3: Process BFS as usual

   Processing all zero in-degree nodes ensures all courses are included in the order.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Queue initialization with all zero in-degree nodes covers disconnected graphs [OK]

Hint: Queue must start with all zero in-degree nodes, not just one [OK]

Common Mistakes:

• Starting BFS from a single node only
• Ignoring disconnected components
• Skipping cycle detection in DFS