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 …


This content originally appeared on DEV Community and was authored by Rakesh Reddy Peddamallu

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!


This content originally appeared on DEV Community and was authored by Rakesh Reddy Peddamallu


Print Share Comment Cite Upload Translate Updates
APA

Rakesh Reddy Peddamallu | Sciencx (2025-08-05T07:47:25+00:00) Leetcode – 210. Course Schedule II. Retrieved from https://www.scien.cx/2025/08/05/leetcode-210-course-schedule-ii/

MLA
" » Leetcode – 210. Course Schedule II." Rakesh Reddy Peddamallu | Sciencx - Tuesday August 5, 2025, https://www.scien.cx/2025/08/05/leetcode-210-course-schedule-ii/
HARVARD
Rakesh Reddy Peddamallu | Sciencx Tuesday August 5, 2025 » Leetcode – 210. Course Schedule II., viewed ,<https://www.scien.cx/2025/08/05/leetcode-210-course-schedule-ii/>
VANCOUVER
Rakesh Reddy Peddamallu | Sciencx - » Leetcode – 210. Course Schedule II. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2025/08/05/leetcode-210-course-schedule-ii/
CHICAGO
" » Leetcode – 210. Course Schedule II." Rakesh Reddy Peddamallu | Sciencx - Accessed . https://www.scien.cx/2025/08/05/leetcode-210-course-schedule-ii/
IEEE
" » Leetcode – 210. Course Schedule II." Rakesh Reddy Peddamallu | Sciencx [Online]. Available: https://www.scien.cx/2025/08/05/leetcode-210-course-schedule-ii/. [Accessed: ]
rf:citation
» Leetcode – 210. Course Schedule II | Rakesh Reddy Peddamallu | Sciencx | https://www.scien.cx/2025/08/05/leetcode-210-course-schedule-ii/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts