Parallel Courses (Minimum Semesters)

▶

Steps

setup

Build graph and indegree array

We create the graph adjacency list and indegree array from the input relations. Each edge from u to v means v depends on u, so indegree[v] increments.

💡 This step sets up the data structures needed to track prerequisites and course dependencies.

Line:

graph = defaultdict(list)
indegree = [0] * (n + 1)
for u, v in relations:
    graph[u].append(v)
    indegree[v] += 1

💡 The indegree array counts how many prerequisites each course has, and the graph shows which courses depend on each prerequisite.

setup

Initialize queue with courses having indegree 0

We enqueue all courses with no prerequisites (indegree 0). These courses can be taken in the first semester.

💡 Starting with courses that have no dependencies is essential to begin the BFS traversal.

Line:

queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])

💡 Courses 1 and 2 have indegree 0, so they are ready to be taken immediately.

setup

Initialize semester and processed count

We set semester count and processed courses count to zero before starting the BFS loop.

💡 These counters track how many semesters have passed and how many courses have been completed.

Line:

semester = 0
processed = 0

💡 Starting counters at zero prepares for the iterative BFS processing.

traverse

Start semester 1: increment semester count

We begin the first semester by incrementing the semester counter. The queue currently holds courses 1 and 2 to be taken this semester.

💡 Incrementing semester count marks the start of a new BFS layer representing one semester.

Line:

semester += 1

💡 Each BFS layer corresponds to one semester of courses taken in parallel.

traverse

Process course 1 in semester 1

We dequeue course 1 to take it this semester. We mark it as processing and increment the processed count.

💡 Processing each course means it is completed this semester, allowing dependent courses to update their prerequisites.

Line:

course = queue.popleft()
processed += 1

💡 Course 1 is now completed, so we can reduce indegree of its dependent courses.

traverse

Update indegree of course 3 after completing course 1

We decrement the indegree of course 3 because one of its prerequisites (course 1) is completed. The edge from 1 to 3 is marked traversed.

💡 Reducing indegree tracks how many prerequisites remain before a course can be taken.

Line:

for nei in graph[course]:
    indegree[nei] -= 1
    if indegree[nei] == 0:
        queue.append(nei)

💡 Course 3 still has one prerequisite (course 2) remaining, so it cannot be taken yet.

traverse

Process course 2 in semester 1

We dequeue course 2 to take it this semester. We mark it as processing and increment the processed count.

💡 Completing course 2 may unlock dependent courses by reducing their indegree.

Line:

course = queue.popleft()
processed += 1

💡 Course 2 is now completed, so we update its dependent courses.

traverse

Update indegree of course 3 after completing course 2

We decrement the indegree of course 3 because its other prerequisite (course 2) is completed. The edge from 2 to 3 is marked traversed. Since indegree is now 0, course 3 is enqueued.

💡 When indegree reaches zero, the course is ready to be taken in the next semester.

Line:

for nei in graph[course]:
    indegree[nei] -= 1
    if indegree[nei] == 0:
        queue.append(nei)

💡 Course 3 is now unlocked and ready for the next semester.

traverse

Start semester 2: increment semester count

We begin the second semester by incrementing the semester counter. The queue holds course 3 to be taken this semester.

💡 Incrementing semester count marks the next BFS layer representing the next semester.

Line:

semester += 1

💡 Semester 2 will process the remaining course 3.

traverse

Process course 3 in semester 2

We dequeue course 3 to take it this semester. We mark it as processing and increment the processed count.

💡 Completing course 3 finishes all courses, allowing us to conclude the algorithm.

Line:

course = queue.popleft()
processed += 1

💡 Course 3 is completed, and no further courses remain.

traverse

Finish processing course 3

Course 3 is marked done. Since no neighbors exist, no indegree updates occur. The queue is empty, ending the BFS loop.

💡 Completing the last course means all courses are done and the algorithm can return the result.

Line:

for nei in graph[course]:
    indegree[nei] -= 1
    if indegree[nei] == 0:
        queue.append(nei)

💡 No further courses to unlock; BFS traversal is complete.

reconstruct

Return semester count as answer

Since all courses have been processed (processed == n), we return the semester count as the minimum semesters needed.

💡 The final semester count represents the minimum number of semesters to complete all courses respecting prerequisites.

Line:

return semester if processed == n else -1

💡 The BFS layering corresponds exactly to the minimum semesters required.

from collections import deque, defaultdict

def min_semesters_optimal(n, relations):
    graph = defaultdict(list)  # STEP 1
    indegree = [0] * (n + 1)  # STEP 1
    for u, v in relations:  # STEP 1
        graph[u].append(v)  # STEP 1
        indegree[v] += 1  # STEP 1

    queue = deque([i for i in range(1, n + 1) if indegree[i] == 0])  # STEP 2
    semester = 0  # STEP 3
    processed = 0  # STEP 3

    while queue:  # STEP 4
        semester += 1  # STEP 4
        for _ in range(len(queue)):  # STEP 5
            course = queue.popleft()  # STEP 5
            processed += 1  # STEP 5
            for nei in graph[course]:  # STEP 6
                indegree[nei] -= 1  # STEP 6
                if indegree[nei] == 0:  # STEP 6
                    queue.append(nei)  # STEP 6

    return semester if processed == n else -1  # STEP 12

if __name__ == '__main__':
    print(min_semesters_optimal(3, [[1,3],[2,3]]))  # Output: 2
    print(min_semesters_optimal(3, [[1,2],[2,3],[3,1]]))  # Output: -1

📊

Parallel Courses (Minimum Semesters) - Watch the Algorithm Execute, Step by Step

Watching each step helps you understand how Kahn's algorithm uses BFS and indegree counts to determine the minimum semesters needed to complete all courses.

Visiting: none

1

2

3

Visiting: none

1

2

3

Queue / Stack

12

Visiting: none

1

2

3

Queue / Stack

12

Visiting: none

1

2

3

Queue / Stack

12

Visiting: 1

1

2

3

Queue / Stack

2

Visiting: 1

Edge: 1 → 3

1

2

3

Queue / Stack

2

Visiting: 2

1

2

3

Visiting: 2

Edge: 2 → 3

1

2

3

Queue / Stack

3

Visiting: none

1

2

3

Queue / Stack

3

Visiting: 3

1

2

3

Visiting: 3

1

2

3

Visiting: none

1

2

3

Key Takeaways

✓ Kahn's algorithm layers courses by semesters using BFS on nodes with zero indegree.

This layering is hard to see from code alone but becomes clear when watching the queue evolve semester by semester.

✓ Indegree counts track how many prerequisites remain before a course can be taken.

Visualizing indegree decrementing and queue insertion clarifies how dependencies unlock courses.

✓ The queue contents at each step represent courses that can be taken in parallel in the current semester.

Seeing the queue state change stepwise reveals the parallelism inherent in the problem.

Practice

1. You are given a directed graph where each node represents a state, and edges represent transitions. Some states lead to cycles, while others eventually lead to terminal states with no outgoing edges. Which algorithmic approach guarantees finding all states that are "eventually safe" (i.e., cannot reach any cycle) in an efficient manner?

easy

A. Use a greedy approach to repeatedly remove nodes with no outgoing edges until no nodes remain.

B. Construct the reverse graph and apply Kahn's algorithm (topological sort using in-degree) to identify safe nodes.

C. Apply dynamic programming with memoization on node states to mark safe and unsafe nodes.

D. Perform a brute force DFS from each node to detect cycles and mark safe nodes accordingly.

Solution

1. Step 1: Understand problem requirements

   The problem requires identifying nodes that cannot reach any cycle, i.e., nodes that eventually lead to terminal nodes.

2. Step 2: Recognize optimal approach

   Reversing the graph and applying Kahn's algorithm on in-degree allows us to efficiently find all nodes that lead to terminal nodes by processing nodes with zero out-degree in the original graph.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Reverse graph + Kahn's algorithm is the known optimal solution for eventual safe states [OK]

Hint: Reverse graph + Kahn's algorithm finds safe nodes efficiently [OK]

Common Mistakes:

• Confusing brute force DFS with optimal topological approach
• Assuming greedy removal without reversing graph suffices
• Misapplying DP without graph reversal

2. You are given an undirected tree with n nodes. The task is to find all nodes that, when chosen as roots, produce trees with minimum height. Which algorithmic approach best guarantees an optimal solution for this problem?

easy

A. Iteratively remove leaf nodes layer by layer until 1 or 2 centroids remain.

B. Use dynamic programming to store subtree heights and combine results.

C. Run BFS/DFS from every node to calculate tree height and pick minimum roots.

D. Apply a greedy approach by always choosing the node with maximum degree as root.

Solution

1. Step 1: Understand the problem structure

   The problem asks for nodes that minimize tree height when chosen as roots. This corresponds to finding centroids of the tree.

2. Step 2: Identify the correct approach

   Iteratively trimming leaves (nodes with degree 1) layer by layer reduces the tree towards its centroids. This approach guarantees finding the minimum height roots efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Leaf trimming is the known optimal pattern for Minimum Height Trees [OK]

Hint: Leaf trimming finds centroids efficiently [OK]

Common Mistakes:

• Thinking BFS from each node is efficient
• Confusing DP with leaf trimming
• Greedy max-degree node is incorrect

3. What is the time complexity of the optimal alien dictionary solution using BFS topological sort on the graph constructed from the input words, where C is the total number of characters in all words, U is the number of unique characters, and E is the number of edges in the graph?

medium

A. O(C * U * E) due to nested loops over characters and edges

B. O(C^2) because all pairs of characters are compared in the worst case

C. O(U^2) since each character can be compared with every other character

D. O(C + U + E) because building the graph and BFS traversal each take linear time in input size and graph size

Solution

1. Step 1: Analyze graph construction

   Building graph edges requires comparing adjacent words once, total O(C) characters processed.

2. Step 2: Analyze BFS topological sort

   Traversal visits each node (U) and edge (E) once, total O(U + E).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sum of graph build and BFS traversal is O(C + U + E) [OK]

Hint: Graph build + BFS traversal linear in input and graph size [OK]

Common Mistakes:

• Assuming quadratic complexity due to pairwise comparisons
• Ignoring that edges are at most U^2 but usually less
• Confusing total characters with unique characters

4. Consider the following buggy code snippet for the alien dictionary problem. Which line contains the subtle bug that can cause incorrect results on inputs where a word is a prefix of the next word?

from collections import defaultdict, deque

def alienOrder(words):
    graph = defaultdict(set)
    in_degree = {c: 0 for word in words for c in word}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i + 1]
        min_len = min(len(w1), len(w2))
        # BUG: Missing prefix invalid case check here
        for j in range(min_len):
            if w1[j] != w2[j]:
                if w2[j] not in graph[w1[j]]:
                    graph[w1[j]].add(w2[j])
                    in_degree[w2[j]] += 1
                break

    queue = deque([c for c in in_degree if in_degree[c] == 0])
    order = []
    while queue:
        c = queue.popleft()
        order.append(c)
        for nei in graph[c]:
            in_degree[nei] -= 1
            if in_degree[nei] == 0:
                queue.append(nei)
    if len(order) < len(in_degree):
        return ""
    return "".join(order)

medium

A. Line missing prefix invalid case check before edge addition

B. Line initializing in_degree dictionary

C. Line checking if w1[j] != w2[j] to add edge

D. Line decrementing in_degree of neighbors in BFS loop

Solution

1. Step 1: Identify prefix invalid case

   If a longer word is prefix of a shorter next word (e.g., "abc" before "ab"), the order is invalid and must return "".

2. Step 2: Locate missing check

   The code lacks the check: if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]: return "" before adding edges.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing prefix check causes incorrect order or silent failure [OK]

Hint: Prefix invalid case must be checked before edge addition [OK]

Common Mistakes:

• Ignoring prefix invalid case leads to wrong output
• Misplacing in-degree initialization
• Incorrectly decrementing in-degree in BFS

5. Examine the following code snippet for finding Minimum Height Trees. Which line contains a subtle bug that causes incorrect results on single-node trees?

medium

A. Missing explicit check for n == 1 at the start

B. Line initializing leaves with nodes of degree 1

C. Line decrementing remaining_nodes by leaves_count

D. Line updating degree[nei] after removing a leaf

Solution

1. Step 1: Identify edge case handling

   The code lacks a special case for n=1, so leaves initialization is empty and the loop never runs, returning an empty list.

2. Step 2: Understand impact of missing check

   Without returning [0] for single-node tree, the function returns incorrect empty result.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single-node tree must be handled explicitly [OK]

Hint: Check for single-node tree before main logic [OK]

Common Mistakes:

• Forgetting n=1 case
• Incorrect leaves initialization
• Not updating degrees properly