Skip to content

summary.en.md

Latest commit

 

History

History
165 lines (123 loc) · 8.93 KB

summary.en.md

File metadata and controls

165 lines (123 loc) · 8.93 KB

Course Schedule II - Topological Sort - Leetcode 210

  • Platform: YouTube
  • Channel/Creator: NeetCode
  • Duration: 00:17:10
  • Release Date: Jan 18, 2021
  • Video Link: Watch on YouTube

Disclaimer: This is a personal summary and interpretation based on a YouTube video. It is not official material and not endorsed by the original creator. All rights remain with the respective creators.

This document summarizes the key takeaways from the video. I highly recommend watching the full video for visual context and coding demonstrations.

Before You Get Started

  • I summarize key points to help you learn and review quickly.
  • Simply click on Ask AI links to dive into any topic you want.

AI-Powered buttons

Teach Me: 5 Years Old | Beginner | Intermediate | Advanced | (reset auto redirect)

Learn Differently: Analogy | Storytelling | Cheatsheet | Mindmap | Flashcards | Practical Projects | Code Examples | Common Mistakes

Check Understanding: Generate Quiz | Interview Me | Refactor Challenge | Assessment Rubric | Next Steps

Problem Overview

We’re given numCourses (0 to n-1) and a list of prerequisite pairs [course, prereq] where you must take prereq before course.
The goal is to return any valid order to finish all courses. If a cycle exists (impossible to finish everything), return an empty array.

Classic example:

  • numCourses = 2, prerequisites = [[1,0]] → [0,1]
  • Add [[0,1]] → cycle → []

This is a directed graph problem where an edge prereq → course means “take prereq before course”. If the graph has a cycle, no valid order exists.

Ask AI: Course Schedule II problem explanation

Graph Representation

Build an adjacency list where the key is a course and the value is the list of its prerequisites (the courses that must be taken before it (its prerequisites).

prereq_map = {c: [] for c in range(numCourses)}
for course, pre in prerequisites:
    prereq_map[course].append(pre)

So edges go from a course → its prerequisites (reverse of the more common “prereq → course” direction). This direction makes the DFS post-order naturally produce the correct finishing order without reversing at the end.

Ask AI: Building adjacency list for prerequisites

DFS Topological Sort (Post-Order)

The core idea:

  1. Run DFS from a node.
  2. Recursively visit all prerequisites first.
  3. Only after all prerequisites are processed → add the current course to the output (post-order).
  4. Leaves (courses with no prerequisites) get added first → correct order.

We track three states per node:

  • Not visited
  • Visiting (currently in recursion stack / green path)
  • Visited (already added to output)

If we ever hit a node that is “visiting”, we found a cycle.

Ask AI: DFS topological sort post-order

Cycle Detection

Use two sets:

  • visit → nodes already fully processed (added to output)
  • cycle → nodes in the current recursion path

Inside DFS:

if course in cycle:      # back edge to node in current path
    return False
if course in visit:      # already done, safe to skip
    return True

If DFS on any prerequisite returns False, propagate the cycle detection upward.

Ask AI: Cycle detection with recursion stack

Full Working Solution

from typing import List

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # Build adj list: course → [prerequisites]
        prereq_map = {c: [] for c in range(numCourses)}
        for course, pre in prerequisites:
            prereq_map[course].append(pre)
        
        output = []
        visit, cycle = set(), set()
        
        def dfs(course: int) -> bool:
            if course in cycle:
                return False                # cycle detected
            if course in visit:
                return True                 # already processed
            
            cycle.add(course)               # mark as visiting
            for pre in prereq_map[course]:
                if not dfs(pre):
                    return False
            
            cycle.remove(course)            # done with this node
            visit.add(course)               # mark as fully visited
            output.append(course)           # post-order → safe to take
            return True
        
       
        
        # Need to try every node in case graph is disconnected
        for c in range(numCourses):
            if not dfs(c):
                return []                       # cycle → impossible
        
        return output

This produces a valid order (any valid order is accepted). Runs in O(V + E) time and O(V) space.

Ask AI: Complete Course Schedule II DFS solution

Alternative Approach (Kahn’s Algorithm)

The video sticks to DFS, but the same problem is very often solved with BFS + indegree count (Kahn’s algorithm):

  • Compute indegrees
  • Queue all nodes with indegree 0
  • While queue not empty: pop, reduce indegrees of neighbors, enqueue new zeros
  • If processed all nodes → return order, else cycle

Many people find Kahn’s easier to understand at first, but DFS is shorter code and works great when you’re comfortable with recursion.

Ask AI: Kahn’s algorithm vs DFS topological sort

About the summarizer

I'm Ali Sol, a Backend Developer. Learn more: