Skip to main content
DSA patterns

Course Schedule

mediumGraphs Must-doGoogleMetaUberStripe

Problem statement

You need to take numCourses courses, numbered 0 to numCourses - 1. Some courses require another course to be finished first — a pair [a, b] in prerequisites means you must take course b before you're allowed to take course a.

Given all the prerequisite pairs, return true if it's possible to finish every course, or false if the requirements make that impossible.

This is the same shape as service startup ordering: service A might need service B to already be up before it can start, and the real question is whether that whole web of "needs" can ever be satisfied, or whether two or more services end up needing each other in a loop that can never resolve.

Examples

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true

Explanation: course 1 needs course 0 first, so take course 0, then course 1 — both get finished with no conflict.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

Output: false

Explanation: course 1 needs course 0, but course 0 also needs course 1 — each is stuck waiting on the other, so neither can ever be taken first.

Hints

Hint 1: Picture each course as a node and each prerequisite as a one-way arrow from the course to the thing it needs — the question "can every course be finished" turns into "does this arrow diagram contain a loop".

Approach

Optimal: 2 (Kahn's algorithm — BFS topological sort

Intuition

Instead of exploring one course's chain of requirements at a time, work outward from whatever's already available: any course with zero remaining prerequisites can be taken right now. Take it, and for every course that depended on it, reduce its remaining-requirement count by one — if that count hits zero, it just became available too. Keep taking available courses this way. If every course eventually gets taken, there was no cycle; if the queue runs dry while some courses are still waiting, those leftover courses can only be waiting on each other in a loop.

Steps

  1. Build an adjacency list: for each prerequisite [course, need], add a forward edge from need to course (finishing need unlocks course).
  2. Count each course's in-degree: how many prerequisites still block it.
  3. Put every course with in-degree 0 into a queue — these can be taken immediately.
  4. While the queue isn't empty, take a course out, count it as taken, and for every course it unlocks, decrease that course's in-degree by one.
  5. If a course's in-degree reaches 0, add it to the queue.
  6. Once the queue is empty, return true only if the number of courses taken equals numCourses.

Dry run

numCourses = 2, prerequisites = [[1,0],[0,1]]

Forward edges: 0 → 1 (finishing 0 unlocks 1), 1 → 0 (finishing 1 unlocks 0). In-degrees: course 0 has in-degree 1 (from course 1), course 1 has in-degree 1 (from course 0).

step queue taken action
start [] (neither has in-degree 0) 0 nothing to enqueue at all

The queue starts empty, since both courses have in-degree 1 and neither ever reaches 0 — each is only unlocked by the other, which never gets taken. taken stays at 0, which doesn't equal numCourses (2), so the answer is false.

Edge cases: with no prerequisites at all, every course starts at in-degree 0 and the queue begins with everything already in it; a chain where each course unlocks exactly the next one processes one course per step, in order, until the whole chain is taken.

Complexity

Time O(V + E) - Every course enters the queue at most once, and every prerequisite edge is examined exactly once when its source course is processed, so the total work is proportional to V + E, the same as the DFS approach.

Space O(V + E) - the adjacency lists, the in-degree array, and the queue, which in the worst case holds every course with no prerequisites at once.

from collections import deque


class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        adjacency = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for course, need in prerequisites:
            adjacency[need].append(course)
            indegree[course] += 1

        queue = deque(c for c in range(numCourses) if indegree[c] == 0)
        taken = 0
        while queue:
            course = queue.popleft()
            taken += 1
            for nxt in adjacency[course]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)
        return taken == numCourses


if __name__ == "__main__":
    print(str(Solution().canFinish(2, [[1, 0]])).lower())  # true
    print(str(Solution().canFinish(2, [[1, 0], [0, 1]])).lower())  # false
RecapThe whole problem in a few lines, for the night before
  • Spot it: "can all of these be finished/scheduled" with [a, b] meaning a depends on b
  • Idea: model as a directed graph and check for a cycle — no cycle means a valid order exists
  • Cost: O(V + E) time and space (V courses, E prerequisites); naive repeated-sweep check: O(V·(V+E))
  • Trap: using a single visited flag in DFS instead of distinguishing "on the current path" from "already cleared" — that's the only way to actually catch the cycle

Interview follow-ups

  • What if you also needed to return *one valid order* to take the courses in, not just whether it's possible?

    Both approaches already build this along the way. In Kahn's algorithm, append each course to a result list at the moment it's dequeued — the resulting list is a valid order, since a course can't be dequeued until every prerequisite ahead of it already has been. In DFS, appending a course to the front of a result list right after it's marked 2 (cleared) produces the same kind of valid order, just discovered in the reverse direction.

  • The prerequisite list is enormous and arrives incrementally — new prerequisite pairs keep getting added to a live system. What would you do?

    Adding one new edge only risks creating a cycle through that specific edge, so rather than rechecking the whole graph, check whether the new edge's target can already reach the new edge's source (a single traversal from one node, not the whole graph). If it can, this one addition would close a loop and should be rejected; if not, it's safe to add. This turns an O(V+E) full recheck per addition into one bounded search per addition instead.

  • What if prerequisites came with weights (some courses take longer than others), and you needed the fastest possible schedule assuming courses without a dependency between them can run in parallel?

    The cycle check itself is unchanged — a cycle still makes the whole schedule impossible regardless of weights. Once you know it's acyclic, computing the fastest possible finish time becomes a longest-path problem on the same graph, using Kahn's ordering: process courses in topological order, and for each one, its earliest finish time is its own duration plus the maximum finish time among everything it depends on. That's still O(V + E), just doing slightly more arithmetic per course instead of a simple boolean check.

Frequently asked questions

Swap "course" for "service", "package", or "database migration" and this is exactly startup-ordering and dependency-resolution: can every service in a deployment come up given what each one depends on, and is there a circular dependency (A needs B, B needs A) that would deadlock the rollout forever? Build tools, package managers, and Kubernetes-style dependent workloads all run some version of this same cycle check before doing anything.

Because the underlying fact being checked — whether the dependency graph has a cycle — doesn't depend on the order courses are visited in, only on the graph's actual structure. DFS finds a cycle by noticing it revisits a course still active on the current exploration path; BFS finds the same fact by noticing some courses never reach zero remaining prerequisites. Different bookkeeping, same underlying graph property, same O(V + E) cost.

A plain visited flag can't tell the difference between "this course is still being actively explored right now" and "this course was fully explored earlier and is safe." Both look like "already seen" with only two states, but only the first one signals a cycle. The middle state — "on the current path" — is what lets the algorithm tell those two very different situations apart.

It means that specific course, and everything else stuck with it, only had prerequisites pointing back into that same stuck group — none of them ever reached zero required prerequisites, because they were all still waiting on each other. That leftover group is precisely the cycle (or the set of courses downstream of one), even though Kahn's algorithm never explicitly names which courses form the loop.