Course Schedule II (Topological Order)

▶

Steps

setup

Initialize graph and in-degree array

Create an adjacency list for all courses and initialize an in-degree array with zeros for each course.

💡 This sets up the data structures needed to track prerequisites and how many courses depend on each course.

Line:

graph = defaultdict(list)
in_degree = [0] * numCourses

💡 We need to represent the graph and track in-degree counts before processing.

setup

Build graph and compute in-degree for each course

For each prerequisite pair [a, b], add an edge from b to a and increment in-degree of a.

💡 This step encodes the prerequisite relationships and counts how many prerequisites each course has.

Line:

for a, b in prerequisites:
    graph[b].append(a)
    in_degree[a] += 1

💡 Edges represent dependencies; in-degree counts how many prerequisites remain for each course.

setup

Initialize queue with courses having zero in-degree

Add all courses with zero in-degree to the queue as they have no prerequisites and can be taken immediately.

💡 Starting with courses that have no prerequisites allows the algorithm to build the order from the ground up.

Line:

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

💡 Courses with zero in-degree are ready to be processed first.

traverse

Process course 0 from queue

Pop course 0 from the queue and add it to the order. Mark it as processing.

💡 Taking course 0 first is valid because it has no prerequisites.

Line:

node = queue.popleft()
order.append(node)

💡 Removing a node with zero in-degree means we can now consider its dependent courses.

traverse

Decrement in-degree of neighbor course 1

For neighbor course 1 of course 0, decrement its in-degree by 1 and mark the edge as traversed.

💡 Reducing in-degree reflects that one prerequisite has been completed.

Line:

for nei in graph[node]:
    in_degree[nei] -= 1

💡 Updating in-degree helps identify when a course becomes available to take.

traverse

Add course 1 to queue as its in-degree is zero

Since course 1's in-degree is now zero, add it to the queue and mark its state as in_queue.

💡 Courses with zero in-degree are ready to be taken next.

Line:

if in_degree[nei] == 0:
    queue.append(nei)

💡 Queue updates reflect newly available courses to process.

traverse

Decrement in-degree of neighbor course 2

For neighbor course 2 of course 0, decrement its in-degree by 1 and mark the edge as traversed.

💡 Each prerequisite completion reduces the in-degree of dependent courses.

Line:

for nei in graph[node]:
    in_degree[nei] -= 1

💡 Tracking in-degree changes is key to knowing when courses become available.

traverse

Add course 2 to queue as its in-degree is zero

Since course 2's in-degree is now zero, add it to the queue and mark its state as in_queue.

💡 Newly available courses are enqueued to be processed in order.

Line:

if in_degree[nei] == 0:
    queue.append(nei)

💡 Queue contents dynamically update as courses become available.

traverse

Process course 1 from queue

Pop course 1 from the queue and add it to the order. Mark it as processing.

💡 Course 1 can now be taken as all its prerequisites are done.

Line:

node = queue.popleft()
order.append(node)

💡 Processing courses in queue order respects prerequisite constraints.

traverse

Decrement in-degree of neighbor course 3 from course 1

Decrease in-degree of course 3 by 1 due to completion of course 1 and mark the edge as traversed.

💡 Each prerequisite completion reduces the in-degree of dependent courses, moving them closer to availability.

Line:

for nei in graph[node]:
    in_degree[nei] -= 1

💡 Tracking in-degree changes is essential to know when courses become available.

traverse

Course 3 not added to queue yet (in-degree not zero)

Since course 3's in-degree is still 1, it is not added to the queue yet.

💡 Courses are only added to the queue when all prerequisites are completed (in-degree zero).

Line:

if in_degree[nei] == 0:
    queue.append(nei)

💡 In-degree acts as a gatekeeper for course availability.

traverse

Process course 2 from queue

Pop course 2 from the queue and add it to the order. Mark it as processing.

💡 Course 2 is now ready to be taken as all its prerequisites are done.

Line:

node = queue.popleft()
order.append(node)

💡 Processing courses in queue order respects prerequisite constraints.

traverse

Decrement in-degree of neighbor course 3 from course 2

Decrease in-degree of course 3 by 1 due to completion of course 2 and mark the edge as traversed.

💡 Completing another prerequisite reduces course 3's in-degree to zero.

Line:

for nei in graph[node]:
    in_degree[nei] -= 1

💡 When in-degree reaches zero, the course becomes available.

traverse

Add course 3 to queue as its in-degree is zero

Since course 3's in-degree is zero, add it to the queue and mark its state as in_queue.

💡 Course 3 is now available to be taken after all prerequisites are done.

Line:

if in_degree[nei] == 0:
    queue.append(nei)

💡 Queue updates reflect the dynamic availability of courses.

traverse

Process course 3 from queue

Pop course 3 from the queue and add it to the order. Mark it as processing.

💡 Course 3 is the last course and can now be taken.

Line:

node = queue.popleft()
order.append(node)

💡 Processing the last course completes the topological order.

traverse

No neighbors to process for course 3

Course 3 has no neighbors, so no in-degree updates are needed.

💡 Leaf nodes in the graph have no dependent courses.

Line:

for nei in graph[node]:
    # no neighbors here

💡 Processing ends when no neighbors remain to update.

traverse

Mark course 3 as done and finalize order

Mark course 3 as done and add it to visited. The queue is empty, so processing ends.

💡 All courses have been processed in a valid order.

Line:

order.append(node)
# queue empty, end loop

💡 Completion of all nodes means a valid topological order is found.

reconstruct

Check if all courses processed and return order

Since the order contains all courses, return the order as the valid topological sort.

💡 If all courses are included, the order is a valid schedule.

Line:

if len(order) == numCourses:
    return order

💡 Successful topological sort means no cycles and all prerequisites met.

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)  # STEP 1
    in_degree = [0] * numCourses  # STEP 1
    for a, b in prerequisites:  # STEP 2
        graph[b].append(a)  # STEP 2
        in_degree[a] += 1  # STEP 2

    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])  # STEP 3
    order = []

    while queue:  # STEP 4
        node = queue.popleft()  # STEP 4
        order.append(node)  # STEP 4
        for nei in graph[node]:  # STEP 5
            in_degree[nei] -= 1  # STEP 5
            if in_degree[nei] == 0:  # STEP 6
                queue.append(nei)  # STEP 6

    if len(order) == numCourses:  # STEP 7
        return order  # STEP 7
    else:
        return []

if __name__ == '__main__':
    print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

📊

Course Schedule II (Topological Order) - Watch the Algorithm Execute, Step by Step

Watching each step visually reveals how Kahn's Algorithm uses in-degree counts and a queue to find a valid course order, making the abstract concept concrete.

Visiting: none

0

1

2

3

Visiting: none

0

1

2

3

Visiting: none

0

1

2

3

Queue / Stack

0

Visiting: 0

0

1

2

3

Visiting: 0

Edge: 0 → 1

0

1

2

3

Visiting: 0

Edge: 0 → 1

0

1

2

3

Queue / Stack

1

Visiting: 0

Edge: 0 → 2

0

1

2

3

Queue / Stack

1

Visiting: none

0

1

2

3

Queue / Stack

12

Visiting: 1

0

1

2

3

Queue / Stack

2

Visiting: 1

Edge: 1 → 3

0

1

2

3

Queue / Stack

2

Visiting: none

0

1

2

3

Queue / Stack

2

Visiting: 2

0

1

2

3

Visiting: 2

Edge: 2 → 3

0

1

2

3

Visiting: none

0

1

2

3

Queue / Stack

3

Visiting: 3

0

1

2

3

Visiting: 3

0

1

2

3

Visiting: none

0

1

2

3

Key Takeaways

✓ Kahn's Algorithm uses in-degree counts and a queue to iteratively find courses with no remaining prerequisites.

This insight is hard to see from code alone because the dynamic changes in in-degree and queue contents are abstract without visualization.

✓ The graph edges represent prerequisite dependencies, and decrementing in-degree simulates completing prerequisites.

Seeing edges change state and in-degree update visually clarifies how dependencies are resolved step-by-step.

✓ Courses are only added to the queue when their in-degree reaches zero, ensuring a valid order respecting all prerequisites.

The decision to enqueue or not is critical and is easier to understand when watching the queue evolve during the trace.

Practice

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

2. You are given a list of sequences, each representing partial orderings of elements. Your task is to determine if there exists exactly one sequence that can be constructed which is consistent with all these partial orderings and matches a given original sequence. Which algorithmic approach best guarantees an efficient and correct solution for this problem?

easy

A. Use brute force to generate all permutations of the original sequence and check which ones are supersequences of all given sequences.

B. Apply a greedy approach by always choosing the smallest available element not yet placed, hoping to build the unique sequence.

C. Use dynamic programming to count the number of ways to interleave the sequences and verify if only one matches the original.

D. Construct a directed graph from the sequences and perform a DFS postorder topological sort with cycle detection and uniqueness verification.

Solution

1. Step 1: Understand problem constraints

   The problem requires verifying if exactly one sequence matches all partial orderings, which is a classic unique topological order problem.

2. Step 2: Identify suitable algorithm

   Brute force is inefficient; greedy and DP approaches do not guarantee correctness or uniqueness checks. DFS postorder topological sort with cycle detection and uniqueness verification efficiently solves the problem.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DFS topological sort with uniqueness check is standard for unique sequence reconstruction [OK]

Hint: Unique topo order requires graph + DFS with uniqueness check [OK]

Common Mistakes:

• Assuming greedy or DP can guarantee uniqueness
• Trying brute force despite factorial complexity

3. What is the time complexity of the optimal approach that uses the reversed graph and Kahn's algorithm to find eventual safe states in a graph with V vertices and E edges?

medium

A. O(V + E) because each edge and vertex is processed once during graph reversal and BFS

B. O(V^2) because we process each node and its neighbors repeatedly

C. O(V * E) due to nested loops over vertices and edges

D. O(E log V) because of sorting the safe nodes at the end

Solution

1. Step 1: Analyze graph reversal and in-degree computation

   Reversing the graph and computing in-degree requires iterating over all edges once, O(E).

2. Step 2: Analyze BFS processing

   Each node is enqueued and dequeued at most once, and each edge is considered once when decrementing in-degree, total O(V + E).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time in vertices and edges matches BFS and graph reversal [OK]

Hint: Each edge and vertex processed once in BFS + reversal [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing sorting cost as dominant
• Forgetting BFS processes each edge once

4. Suppose the alien dictionary problem is extended so that characters can appear multiple times in the same word and the order must reflect the first occurrence precedence only. Which modification to the topological sort approach correctly handles this variant without breaking correctness or efficiency?

hard

A. Modify graph construction to add edges for every differing character pair in all positions, not just first differing character

B. Use a brute force approach comparing all pairs of words and all character positions to build edges

C. Keep only the first differing character pair between adjacent words to add edges, ignoring subsequent differences

D. Ignore repeated characters and treat each character as unique node per occurrence

Solution

1. Step 1: Understand variant requirement

   Order depends only on first differing character between adjacent words, even if characters repeat later.

2. Step 2: Confirm correct approach

   Adding edges only for the first differing character pair preserves partial order and avoids cycles or redundant edges.

3. Step 3: Reject incorrect modifications

   Adding edges for all differing pairs or treating repeated chars as unique nodes breaks correctness or efficiency.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   First differing character edge addition is minimal and sufficient [OK]

Hint: Only first differing character pair defines order [OK]

Common Mistakes:

• Adding edges for all differing pairs causing cycles
• Using brute force all pairs approach losing efficiency
• Treating repeated chars as distinct nodes

5. Suppose the problem is modified so that nodes can be revisited multiple times along a path (cycles allowed), and you want the largest color value on any path (possibly infinite). Which of the following approaches correctly handles this variant?

hard

A. Detect cycles and return -1 immediately since infinite paths exist

B. Use the original topological sort + DP approach, ignoring cycles

C. Use DFS with memoization and cycle detection to find maximum color counts on simple paths only

D. Apply Bellman-Ford style relaxation over multiple iterations to handle cycles and update color counts

Solution

1. Step 1: Understand impact of cycles

   Allowing cycles means paths can be infinitely long, so maximum color count can be unbounded.

2. Step 2: Recognize correct handling

   Detecting cycles and returning -1 is necessary to indicate no finite maximum exists.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Infinite paths imply no finite max color value; cycle detection is mandatory [OK]

Hint: Cycles imply infinite max color count [OK]

Common Mistakes:

• Trying to apply DP ignoring cycles or assuming memoized DFS suffices