Course Schedule

Check whether all courses can be completed.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Course Schedule: Only dequeue zero-indegree courses; removing their outgoing edges may make new courses ready.

Input and goalCheck whether all courses can be completed.

Build the dependency graphThe four prerequisite pairs create edges 0->1, 0->2, 1->3, and 2->3 with indegrees [0,1,1,2].

from\to01230-0->10->2-1---1->32---2->33----

examplecourse_count = 4, prerequisites = [[1,0], [2,0], [3,1], [3,2]]edgeMeaningmatrix cell is prerequisite -> coursecompleted0

Recognize it

Directed prerequisite pairs ask whether every node can be placed after all requirements; failure to process every node means a directed cycle blocks the remainder.

Keep true

Every queued course has indegree zero in the remaining graph, completed counts dequeued courses, and each outgoing edge is removed exactly once when its prerequisite completes.

Reuse it

Repeatedly remove entities with no unmet requirements and decrement their dependents; the same mechanism orders builds, recipes, jobs, and dependency migrations, while leftovers certify a cycle.

Pattern: Topological sort with requirement counts.

Simple idea: Start with courses that need nothing. Completing one course removes one requirement from every course that follows it.

from collections import deque

def can_finish(course_count: int, prerequisites: list[list[int]]) -> bool:
   graph = [[] for _ in range(course_count)]
   indegree = [0] * course_count

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

   ready = deque(course for course in range(course_count) if indegree[course] == 0)
   completed = 0

   while ready:
      course = ready.popleft()
      completed += 1
      for next_course in graph[course]:
         indegree[next_course] -= 1
         if indegree[next_course] == 0:
            ready.append(next_course)

   return completed == course_count

Cost: $O(V+E)$ time and space.