Course Schedule

Problem

Package managers and build systems need to verify that dependency graphs are acyclic before executing a build plan. Given numCourses and a list of prerequisite pairs where [a, b] means course b must be taken before course a, determine if it is possible to finish all courses.

Example 1:

Input: numCourses = 3, prerequisites = [[1,0],[2,1]]
Output: True
Explanation: take course 0 first, then course 1, then course 2.

Example 2:

Input: numCourses = 3, prerequisites = [[1,2],[2,1]]
Output: False
Explanation: course 1 requires course 2 and course 2 requires course 1, so course 1, course 2, and anything depending on them cannot be taken.

Example 3:

Input: numCourses = 4, prerequisites = [[3,0],[0,1],[1,2]]
Output: True
Explanation: the prerequisites form a linear chain 2 -> 1 -> 0 -> 3.

Constraints:

• 1 <= numCourses <= 1000
• 0 <= prerequisites.length <= 2000
• prerequisites[i].length == 2
• 0 <= a, b < numCourses
• All the pairs prerequisites[i] are unique.

Solution Breakdown

Approach: Kahn's algorithm - topological sort by repeatedly peeling off in-degree-0 nodes; cycle detected by a short count.

Model each course as a node and each pair [course, prereq] as a directed edge prereq -> course, so adjacency[prereq] lists the courses that prereq unlocks, and in_degree[course] counts how many prerequisites still block it. Seed the queue with every node whose in-degree is already 0 - those depend on nothing and can be taken first. The loop pops a node, counts it as completed, and decrements the in-degree of each course it unlocks; any course that drops to in-degree 0 has all its prerequisites satisfied and joins the queue. This removal order is a valid topological order because a node is only released after every edge into it has been resolved. The cycle test is implicit: if completed == num_courses, every course was eventually freed, so no cycle. If the loop drains the queue with completed < num_courses, the leftover courses each still wait on one another - that mutual wait is the cycle, and no ordering exists. Trace [[0,1],[1,2],[2,0]] (Example 5 data, the three-node cycle): every course has in-degree 1, the seed queue is empty, the loop never runs, completed stays 0, and the function returns False.

Edge cases: No prerequisites means every course starts at in-degree 0 and all are processed (returns True). A self-loop or any cycle leaves nodes permanently above in-degree 0, so they are never queued.

Complexity: O(V + E) time, O(V + E) space - each node is enqueued once, each edge is decremented once, and the adjacency list dominates the space.