LeetCode 207 · Graphs

Course Schedule, explained with a picture

Can every course be taken?.

MediumGraphs
▶ Watch it step by step

The problem

There are n courses. Each prerequisite pair “a needs b” means you must take b before a. Can you finish all courses? (Impossible only if the requirements form a loop.)

Input:  n = 4, prerequisites 1-0, 2-0, 3-1, 3-2  (“1 needs 0”, …)
Output: true

Picture it

Picture each course as a circle with arrows from a course to the courses that need it. A course with no remaining prerequisites can be taken right now. Take it and cross out its arrows; that may free up other courses. If we end up taking every course, it’s possible. If some courses are stuck waiting on each other (a loop), it isn’t.

How to recognise it

  • Items with "must come before" rules: courses, build steps, tasks with dependencies.
  • The rules form a directed graph, and the question is whether an order exists that respects all of them.
  • An order is impossible exactly when the rules form a cycle (A needs B, B needs C, C needs A).
  • Up to 2,000 courses and 5,000 rules: repeating a full search for every course is wasteful, and trying orderings is hopeless.

Start with brute force

A course is stuck if following "is a prerequisite of" arrows leads back to itself. So for each course, walk everything that depends on it, and report failure if the walk comes back to the start.

def can_finish_brute(n, prerequisites):
    nxt = defaultdict(list)
    for course, need in prerequisites:
        nxt[need].append(course)
    for start in range(n):
        seen, st = set(), list(nxt[start])
        while st:
            x = st.pop()
            if x == start:
                return False
            if x not in seen:
                seen.add(x)
                st.extend(nxt[x])
    return True

Each of the n starts may walk the whole graph, so time is O(V·(V + E)). With V = 2,000 and E = 5,000 that is about 1.4 × 10^7 steps, which is fine here, but with 10^5 courses and rules it would be about 10^10. Space is O(V + E).

From brute force to the idea

  1. Find the waste. The brute force re-walks the same parts of the graph from each start, only to ask one yes/no question.
  2. Think like a student. A course with no unmet prerequisites can be taken right now. Taking it may free others.
  3. Count unmet prerequisites. indeg[c] is the number of prerequisites of c. nxt[need] lists the courses that wait for need.
  4. Peel off the free courses. Queue every course with indeg == 0. When you take one, reduce indeg of each course that was waiting for it, and queue any that reaches 0. This is Kahn's algorithm.
  5. Count what you took. Courses on a cycle wait for each other and never reach 0, so they are never taken. If len(taken) == n, there is no cycle.

The key idea: repeatedly take what is free, and a cycle shows up as courses that never become free.

The key idea

Kahn’s topological sort: count incoming arrows, repeatedly take courses with count 0. All taken ⇔ no cycle.

Python solution

def can_finish(n, prerequisites):
    indeg = [0] * n; nxt = defaultdict(list)
    for course, need in prerequisites:
        nxt[need].append(course); indeg[course] += 1
    q = deque(c for c in range(n) if indeg[c] == 0)
    taken = []
    while q:
        c = q.popleft()
        taken.append(c)
        for d in nxt[c]:
            indeg[d] -= 1
            if indeg[d] == 0:
                q.append(d)
    return len(taken) == n

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict, deque

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(V·(V + E)): a walk from every courseO(V + E): the adjacency lists and a seen set
Kahn's algorithm (shown code)O(V + E): each course is queued once and each rule is processed onceO(V + E): the adjacency lists, in-degrees, queue and taken

Edge cases

  • No prerequisites (n = 3, []): returns True.
  • A course that needs itself ([[0, 0]]): returns False, since it never reaches 0.
  • A two-course loop ([[0,1],[1,0]]): returns False.
  • A loop plus free courses (n = 3, [[1,0],[1,2],[2,1]]): course 0 is taken but 1 and 2 are not, so the result is False.
  • Duplicate rules ([[1,0],[1,0]]): counted twice in indeg and decremented twice, so the result is True.
  • n = 0: returns True. The shown code needs deque and defaultdict imported.

Common mistakes

  • Reversing the edge direction (nxt[course] instead of nxt[need]) so the in-degrees and the arrows disagree.
  • Returning after the first course with indeg == 0 without checking that all n were taken.
  • Treating the rules as undirected, which cannot tell a real loop from two courses linked in one direction.
  • Forgetting courses that never appear in any rule, which still count towards n.
  • Using recursion for a deep chain of 2,000 courses without checking the recursion limit.
Your turn: how many semesters?

You can take any number of courses per semester, but only those whose prerequisites were taken in an earlier semester. Return the minimum number of semesters to finish all courses, or -1 if impossible. Describe what changes, then write it if you like.

Compare with our answer

Run Kahn's algorithm level by level. Each level is the set of courses that are free at the same moment, so it is one semester.

def min_semesters(n, prerequisites):
    indeg = [0] * n
    nxt = defaultdict(list)
    for course, need in prerequisites:
        nxt[need].append(course)
        indeg[course] += 1
    q = deque(c for c in range(n) if indeg[c] == 0)
    taken, semesters = 0, 0
    while q:
        semesters += 1
        for _ in range(len(q)):
            c = q.popleft()
            taken += 1
            for d in nxt[c]:
                indeg[d] -= 1
                if indeg[d] == 0:
                    q.append(d)
    return semesters if taken == n else -1

Time O(V + E), space O(V + E). The answer is the length of the longest prerequisite chain.

A strong answer mentions: processing the queue in levels, counting a level as a semester, and returning -1 when not all courses were taken.

Check what stuck

1. A build tool reads rules such as "module A must be built before module B" for thousands of modules. It must report whether the rules can be satisfied. Which approach fits best?

2. Why does len(taken) == n tell you that the courses can all be finished?

3. A learner changes the last line to return len(taken) > 0. Which input now returns a wrong answer?

Score 60% or more and the lesson is marked complete.