Course Schedule: Topological Sort Pattern

Learning Outcome

After this lesson, you should be able to model prerequisites as a directed graph and use zero-indegree BFS to detect cycles.

Problem Statement

Given numCourses and prerequisite pairs, return true if all courses can be finished.

Brute Force Approach

Try every possible course order. This is factorial in the number of courses and quickly becomes impossible.

Optimized Approach

Build a directed graph from prerequisite to course. Repeatedly take courses with indegree 0 and count how many courses are removed.

Exact Pseudocode

build graph and indegree
queue = all courses with indegree 0
taken = 0
while queue not empty:
  course = pop front
  taken += 1
  for nextCourse in graph[course]:
    indegree[nextCourse] -= 1
    if indegree[nextCourse] becomes 0:
      push nextCourse
return taken equals numCourses
  

Reference Code

from collections import deque

class Solution:
    def canFinish(self, numCourses, prerequisites):
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

        for course, pre in prerequisites:
            graph[pre].append(course)
            indegree[course] += 1

        q = deque(i for i in range(numCourses) if indegree[i] == 0)
        taken = 0

        while q:
            course = q.popleft()
            taken += 1
            for nxt in graph[course]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    q.append(nxt)

        return taken == numCourses
  

Sample Dry Run

Complexity

Edge Cases

• No prerequisites should return true.
• A cycle leaves some courses with positive indegree.
• Edge direction must be prerequisite to course.

Interview Checklist

• Build indegree from course dependencies.
• Start with all zero-indegree courses.
• Compare taken count with numCourses.

FAQs