Course Schedule II (Topological Order)

📋

Course Schedule II (Topological Order)

Edge cases:

</>

IDE

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:public int[] findOrder(int numCourses, int[][] prerequisites)vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites)function findOrder(numCourses, prerequisites)

def findOrder(numCourses, prerequisites):
    # Write your solution here
    pass

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    // Write your solution here
    return {};
}

function findOrder(numCourses, prerequisites) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Partial order missing some coursesNot processing all zero in-degree nodes or stopping early✅ Initialize queue with all zero in-degree nodes and process until empty, then check if order length equals numCourses

Wrong: Non-empty order despite cycle existingNo cycle detection or incomplete check of processed nodes count✅ Return empty list if processed nodes count is less than numCourses after BFS

Wrong: Incorrect order violating prerequisitesIncorrect in-degree updates or enqueueing nodes prematurely✅ Decrement in-degree of neighbors only after processing a node and enqueue neighbors only when in-degree reaches zero

Wrong: TLE on large inputsUsing brute force permutations or DFS without pruning✅ Implement Kahn's algorithm with O(V+E) complexity using queue and in-degree array

✓

Test Cases

Focus on handling edge cases like empty input and cycles.

Test your cycle detection thoroughly and handle disconnected graphs.

Optimize your solution to linear time complexity using BFS and in-degree arrays.

t1_01basic

Input{"numCourses":4,"prerequisites":[[1,0],[2,0],[3,1],[3,2]]}

Expected[0,2,1,3]

⏱ Performance - must finish in 2000ms

You must take course 0 before 1 and 2, and courses 1 and 2 before 3. One valid order is [0,1,2,3].

💡 Think about representing courses and prerequisites as a graph and finding an order to visit nodes.

💡 Use Kahn's algorithm: track in-degree of each node and repeatedly remove nodes with zero in-degree.

💡 Build an in-degree array, enqueue all zero in-degree nodes, and process until all nodes are ordered.

Why it failed: Basic case failed - likely incorrect in-degree calculation or queue processing. Fix by correctly updating in-degree and only enqueue nodes when in-degree reaches zero.

✓ Core topological order logic using Kahn's algorithm is correct.

t1_02basic

Input{"numCourses":3,"prerequisites":[[1,0],[2,1]]}

Expected[0,1,2]

⏱ Performance - must finish in 2000ms

Course 0 must be taken before 1, and 1 before 2. The only valid order is [0,1,2].

💡 Check how prerequisites form a chain and how that affects the order.

💡 Ensure the algorithm correctly handles linear chains by updating in-degree and queue.

💡 Verify that nodes with zero in-degree are processed first and their neighbors' in-degree updated.

Why it failed: Failed linear chain ordering - likely not updating in-degree or queue correctly. Fix by decrementing in-degree of neighbors and enqueueing when zero.

✓ Linear chain ordering handled correctly.

t2_01edge

Input{"numCourses":0,"prerequisites":[]}

Expected[]

⏱ Performance - must finish in 2000ms

No courses to take means empty order.

💡 Consider the case when there are no courses at all.

💡 Your algorithm should handle empty input gracefully without errors.

💡 Return an empty list immediately if numCourses is zero.

Why it failed: Fails empty input - likely does not handle numCourses=0 or empty prerequisites. Fix by adding a base case returning empty list if numCourses is zero.

✓ Handles empty input correctly.

t2_02edge

Input{"numCourses":1,"prerequisites":[]}

Expected[0]

⏱ Performance - must finish in 2000ms

Single course with no prerequisites should return that course.

💡 Check how your algorithm handles a single node with no edges.

💡 The in-degree of the single course should be zero, so it should be returned.

💡 Ensure your queue initialization includes all zero in-degree nodes, including single nodes.

Why it failed: Fails single course case - likely queue initialization or output construction error. Fix by including all zero in-degree nodes in the initial queue.

✓ Single course with no prerequisites handled correctly.

t2_03edge

Input{"numCourses":3,"prerequisites":[[0,1],[1,2],[2,0]]}

Expected[]

⏱ Performance - must finish in 2000ms

Cycle exists among courses 0,1,2, so no valid order exists.

💡 Detect cycles by checking if all nodes are processed in topological order.

💡 If the output order length is less than numCourses, a cycle exists.

💡 Return empty list if cycle detected by comparing processed count with numCourses.

Why it failed: Fails cycle detection - likely does not check if all nodes are processed. Fix by returning empty list if processed nodes count < numCourses.

✓ Cycle detection and empty output handled correctly.

t2_04edge

Input{"numCourses":2,"prerequisites":[]}

Expected[1,0]

⏱ Performance - must finish in 2000ms

No prerequisites means any order of courses is valid; here [0,1] is expected.

💡 When no prerequisites exist, all courses have zero in-degree.

💡 Your algorithm should enqueue all courses initially.

💡 Return any valid order including all courses.

Why it failed: Fails no prerequisites case - likely not initializing queue with all courses. Fix by enqueueing all zero in-degree nodes at start.

✓ Handles no prerequisites case correctly.

t3_01corner

Input{"numCourses":4,"prerequisites":[[1,0],[2,0],[3,1],[3,2],[1,3]]}

Expected[]

⏱ Performance - must finish in 2000ms

Cycle exists due to 1->3 and 3->1, so no valid order.

💡 Check for cycles that are not obvious linear chains.

💡 Ensure your cycle detection works for cycles involving multiple nodes.

💡 Verify that the algorithm returns empty list when cycle detected anywhere in graph.

Why it failed: Fails to detect complex cycle - likely only detects simple cycles or misses back edges. Fix by verifying processed nodes count equals numCourses after BFS.

✓ Detects complex cycles correctly.

t3_02corner

Input{"numCourses":5,"prerequisites":[[1,0],[2,0],[3,1],[4,2]]}

Expected[0,2,4,1,3]

⏱ Performance - must finish in 2000ms

Multiple disconnected components with valid order including all courses.

💡 Handle multiple disconnected components by processing all zero in-degree nodes.

💡 Ensure all components are included in the final order.

💡 Check that the queue initialization includes all zero in-degree nodes from all components.

Why it failed: Fails to include all disconnected components - likely stops early or misses zero in-degree nodes. Fix by initializing queue with all zero in-degree nodes and processing until empty.

✓ Handles multiple disconnected components correctly.

t3_03corner

Input{"numCourses":4,"prerequisites":[[1,0],[2,0],[3,1],[3,2],[2,1]]}

Expected[0,1,2,3]

⏱ Performance - must finish in 2000ms

Tests correct ordering when multiple prerequisites exist for a course.

💡 Ensure that all prerequisites are respected in the order.

💡 Check that in-degree is correctly updated for all edges.

💡 Verify that nodes are only added to the order when all their prerequisites are processed.

Why it failed: Fails multiple prerequisites ordering - likely incorrect in-degree updates or premature node addition. Fix by decrementing in-degree for all neighbors and enqueue only when zero.

✓ Correctly handles multiple prerequisites per course.

t4_01performance

Input{"numCourses":100,"prerequisites":[[0,1],[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]]}

Expectednull

⏱ Performance - must finish in 2000ms

Chain of 100 courses with linear prerequisites, n=100, O(V+E) must complete in 2s.

💡 Use O(V+E) BFS topological sort with in-degree array and queue.

💡 Avoid recomputing in-degree or scanning entire graph repeatedly.

💡 Process nodes with zero in-degree efficiently using a queue.

Why it failed: TLE due to exponential or factorial complexity (e.g., brute force permutations). Fix by implementing Kahn's algorithm with O(V+E) complexity.

✓ Algorithm runs in O(V+E) time confirming performance.

Practice

1. You are given a list of words sorted lexicographically in an unknown language. Your task is to determine the order of characters in this alien language. Which algorithmic approach guarantees an optimal solution to infer the character order from these constraints?

easy

A. Topological sort on a directed graph constructed from character precedence relations inferred from adjacent words

B. Greedy algorithm that picks the first differing character between adjacent words and orders them immediately

C. Dynamic programming to find the longest common subsequence between all pairs of words

D. Brute force comparison of all pairs of words to deduce character order by frequency

Solution

1. Step 1: Understand problem constraints

   The problem requires inferring a partial order of characters based on lexicographical ordering of words, which naturally forms a directed graph of precedence relations.

2. Step 2: Identify suitable algorithm

   Topological sort is the standard algorithm to find a linear order of nodes in a directed acyclic graph (DAG), which fits perfectly to infer character order from precedence edges.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Topological sort handles partial orders and cycles correctly [OK]

Hint: Partial order inference -> topological sort [OK]

Common Mistakes:

• Assuming greedy approach works without cycle detection
• Confusing longest common subsequence with order inference
• Using brute force frequency counts which ignore order

2. Consider the following iterative DFS code to find all paths from source (0) to target in a DAG:

from typing import List

def allPathsSourceTarget(graph: List[List[int]]) -> List[List[int]]:
    target = len(graph) - 1
    res = []
    stack = [(0, [0])]

    while stack:
        node, path = stack.pop()
        if node == target:
            res.append(path)
        else:
            for nei in graph[node]:
                stack.append((nei, path + [nei]))
    return res

# Input graph: [[1,2],[3],[3],[]]
print(allPathsSourceTarget([[1,2],[3],[3],[]]))

What is the exact output of this code?

easy

A. [[0,1,3],[0,2,3]]

B. [[0,1,3]]

C. [[0,2,3],[0,1,3]]

D. [[0,1,2,3]]

Solution

1. Step 1: Trace stack operations

   Initial stack: [(0,[0])]. Pop (0,[0]), neighbors 1 and 2 pushed: stack=[(1,[0,1]),(2,[0,2])]. Next pop (2,[0,2]), neighbor 3 pushed: stack=[(1,[0,1]),(3,[0,2,3])]. Pop (3,[0,2,3]) -> target reached, add path.

2. Step 2: Continue tracing remaining stack

   Pop (1,[0,1]), neighbor 3 pushed: stack=[(3,[0,1,3])]. Pop (3,[0,1,3]) -> target reached, add path. Result order: [[0,2,3],[0,1,3]].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Stack is LIFO, so last neighbor pushed is processed first [OK]

Hint: Stack pops last pushed neighbor first, reversing neighbor order [OK]

Common Mistakes:

• Assuming neighbors processed in original order
• Confusing BFS order with DFS stack order

3. You are given n courses labeled from 1 to n and a list of prerequisite pairs where each pair [a, b] means you must take course a before course b. You want to find the minimum number of semesters needed to complete all courses if you can take any number of courses in parallel as long as their prerequisites are met. Which algorithmic approach guarantees finding the minimum semesters efficiently?

easy

A. Use dynamic programming to try all subsets of courses and pick the minimal semester count.

B. Use a greedy approach that always picks the course with the fewest prerequisites next.

C. Use a topological sort with BFS (Kahn's Algorithm) to process courses level by level based on in-degree zero nodes.

D. Use depth-first search (DFS) to detect cycles and then schedule courses in reverse postorder.

Solution

1. Step 1: Understand the problem constraints

   The problem requires scheduling courses respecting prerequisites and minimizing semesters, allowing parallel courses per semester.

2. Step 2: Identify the suitable algorithm

   Kahn's Algorithm (topological sort with BFS) processes nodes with zero in-degree in batches (levels), naturally modeling semesters and ensuring minimal semesters.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Level-by-level BFS matches semesters needed [OK]

Hint: Minimum semesters = levels in topological BFS [OK]

Common Mistakes:

• Thinking greedy picking minimal prerequisites works
• Confusing DFS order with minimal semester scheduling
• Trying exponential DP without pruning

4. What is the time complexity of the optimal topological sort + iterative DP solution for the longest path with different adjacent characters problem, given n nodes and m edges?

medium

A. O(n + m), since topological sort and DP each process nodes and edges once

B. O(n * m), because for each node we process all edges multiple times

C. O(n^2), because we must compare characters for every pair of nodes

D. O(m log n), due to sorting edges by character

Solution

1. Step 1: Identify topological sort complexity

   Topological sort runs in O(n + m) by processing each node and edge once.

2. Step 2: Analyze DP updates

   DP iterates over topo order and edges once, updating dp values in O(m) total.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Both steps combined run in O(n + m) [OK]

Hint: Topological sort + DP each O(n + m), total O(n + m) [OK]

Common Mistakes:

• Confusing with O(n * m) due to nested loops
• Assuming character comparisons add extra complexity
• Thinking sorting edges is required

5. What is the time complexity of the optimal leaf trimming algorithm for finding Minimum Height Trees in a tree with n nodes and n-1 edges?

medium

A. O(n²) because each leaf removal requires scanning all nodes.

B. O(n) because each edge and node is processed at most once during trimming.

C. O(n log n) due to priority queue operations for leaf selection.

D. O(n + m) where m is the number of edges, which equals n-1 here.

Solution

1. Step 1: Analyze leaf trimming operations

   Each node is added and removed from the leaves queue at most once. Each edge is visited when decrementing degrees.

2. Step 2: Combine node and edge processing

   Since the graph is a tree, edges = n-1. Total operations proportional to n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time complexity matches leaf trimming algorithm [OK]

Hint: Each node and edge processed once [OK]

Common Mistakes:

• Assuming O(n²) due to nested loops
• Confusing with BFS from each node
• Thinking priority queue is used