Leetcode - 210. Course Schedule II

If you've ever tried stacking books in the correct order without violating any “pre-read” rule (e.g., read Sapiens before Homo Deus), you already get the idea behind this problem.

---

🎯 Problem Statement

You are given numCourses and a list of prerequisites where each pair [a, b] means "to take course a, you must first take course b."
Return a valid ordering of courses you can take to finish all. If impossible (i.e., a cycle exists), return [].

---

🧭 Intuition

This is a classic topological sort problem on a directed graph:

• Nodes → Courses
• Edges → Dependencies (a → b means you need b before a)

If there's a cycle, no valid order exists (you’d be stuck in an infinite loop of "prerequisite-ception").

---

🔍 Approach – DFS Based Topological Sort

We’ll use DFS traversal with the following tracking sets:

• visit: nodes we've fully explored and added to output.
• cycle: nodes we are currently visiting (used to detect cycles).

💡 Key Ideas:

• If we revisit a node in the cycle set → cycle detected!
• Once a course is fully processed, add it to the output list.
• At the end, reverse output to get the correct course order (but in this code, we're adding post-DFS so it's already reversed correctly).

---

🧑‍💻 Code (DFS Version)

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function (numCourses, prerequisites) {
    const prereq = {};
    for (let c = 0; c < numCourses; c++) {
        prereq[c] = [];  // Initialize each course's dependency list
    }

    for (const [crs, pre] of prerequisites) {
        prereq[crs].push(pre);  // Build the adjacency list
    }

    const output = [];
    const visit = new Set();
    const cycle = new Set();

    const dfs = (crs) => {
        if (cycle.has(crs)) return false;     // Cycle detected
        if (visit.has(crs)) return true;      // Already processed

        cycle.add(crs);                       // Add to current path
        for (let pre of prereq[crs]) {
            if (!dfs(pre)) return false;      // Cycle found in recursion
        }
        cycle.delete(crs);                    // Done exploring this path
        visit.add(crs);                       // Mark as visited
        output.push(crs);                     // Add to result
        return true;
    };

    for (let c = 0; c < numCourses; c++) {
        if (!dfs(c)) return [];  // If any course leads to a cycle, return []
    }

    return output;
};

---

📦 Example

findOrder(4, [[1,0],[2,0],[3,1],[3,2]])
// Output: [0,2,1,3] or [0,1,2,3]

Both outputs are valid! As long as all dependencies are respected, multiple valid orders may exist.

---

📈 Time & Space Complexity

Metric	Complexity
Time	O(V + E) where V = numCourses, E = prerequisites.length
Space (Graph)	O(V + E) for adjacency list
Space (DFS)	O(V) for recursion stack + visited sets

---

🔥 Bonus Insight

This is an acyclic directed graph problem. If you're ever asked to "return an order of tasks with dependencies", think Topological Sort — and decide between DFS or Kahn’s BFS algorithm.

---

💬 Final Thoughts

This pattern shows up a lot in backend systems too — think dependency resolution in build tools, or microservices startup order. Understanding topological sort deeply gives you a powerful tool in your engineering toolkit!

---