Course Schedule

The problem

There are numCourses courses, numbered 0 to numCourses - 1. Each pair [course, before] in prerequisites says that course before must be taken before course course. Return true if there is an order that takes every course, and false if there is not.

Example 1

Input: numCourses = 5, prerequisites = [[0, 1], [0, 2], [1, 3], [2, 3], [4, 0]]

Output: true

Each arrow points from a course to one that needs it. Take 3, then 1 and 2, then 0, then 4.

Example 2

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

Output: false

Course 0 needs 1, and 1 needs 0. Neither can go first.

Example 3

Input: numCourses = 3, prerequisites = []

Output: true

No rules at all, so any order works.

Constraints

• 1 ≤ numCourses ≤ 2000 (call it V)
• 0 ≤ prerequisites.length ≤ 5000 (call it E)
• Every pair is different, and no course needs itself.

Clarifying questions

Do we need to return the order?

No, only whether one exists. (Course Schedule II asks for the order, and the same method gives it.)

Can a course have several prerequisites?

Yes. Course 0 in Example 1 needs both 1 and 2.

Can the same pair appear twice?

No. Every pair is different.

Can a course have no rules at all?

Yes. It can be taken at any time.

Spot the pattern

Courses are nodes and each rule is an arrow from the course that comes first to the course that needs it: a directed graph. All courses can be taken exactly when the arrows never form a loop. Putting the nodes of a directed graph in an order that follows every arrow is a topological sort, a kind of graph search, and it fails exactly when there is a cycle.

Solutions

Repeated passesO(V × (V + E))Kahn's algorithmO(V + E)

Show all

There is no middle approach worth its own tab. A depth-first search that looks for a cycle is the other common answer, and it costs the same O(V + E) as Kahn's algorithm.

Repeated passes O(V × (V + E))

The idea

Act like a student. Go through the courses from 0 to the last one. Take any course whose prerequisites are all taken already. Then go through again, because taking a course may have freed others. Stop when a whole pass takes nothing.

If every course is taken by then, the answer is true. If some are left, each of them waits for another course that is also left. Following those waits must go round in a loop, so no order exists.

Why it is correct: a course is taken only after all its prerequisites, so the order of taking is a valid order. And a pass takes nothing only when every remaining course waits on another remaining one.

Walkthrough

pass

0

taken

empty

1. needs[course] = the prerequisites of course
2. progress = True
3. while progress:
4. progress = False
5. for each course not taken yet:
6. if all of needs[course] are taken:
7. take course; progress = True
8. return every course is taken

An arrow from 3 to 1 means course 3 must come before course 1. Sweep the courses 0 to 4 again and again, taking any course whose prerequisites are all taken.

← BackStep →Play1 / 14

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Repeated passes: keep sweeping the courses and take any course whose
    // prerequisites are all taken. Each pass reads every course and every rule.
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> needs = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) needs.add(new ArrayList<>());
        for (int[] prerequisite : prerequisites) needs.get(prerequisite[0]).add(prerequisite[1]);
        boolean[] taken = new boolean[numCourses];
        boolean progress = true;
        while (progress) {
            progress = false;
            for (int course = 0; course < numCourses; course++) {
                if (taken[course]) continue;
                boolean allTaken = true;
                for (int required : needs.get(course)) allTaken &= taken[required];
                if (allTaken) {
                    taken[course] = true;
                    progress = true;
                }
            }
        }
        // A pass that takes nothing means the rest wait on each other in a cycle.
        for (boolean courseTaken : taken) if (!courseTaken) return false;
        return true;
    }
}

Big O

Time O(V × (V + E))Space O(V + E)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The outer while runs one pass at a time. Inside, the for loop checks each course not taken yet, and each check reads that course’s prerequisites. So one pass costs at most V checks plus E rule reads. We count the checks in each pass.

   1. needs[course] = the prerequisites of course
   2. progress = True
   3. while progress:
   4. progress = False
   5. for each course not taken yet:
   6. if all of needs[course] are taken:
   7. take course; progress = True
   8. return every course is taken

2. 2 Count the runs on Example 1

   The table has one column per pass. Each pass checks only the courses still left. The last pass checks nothing and takes nothing, which ends the loop.

   5 + 4 + 2 + 0 = 11 checks, reading at most the 5 rules per pass.

   	pass 1	pass 2	pass 3	pass 4
   courses checked	5	4	2	0
   courses taken	1	2	2	0

   checks

   5 + 4 + 2 + 0 = 11

3. 3 Write the count for any n

   Every pass except the last takes at least one course, so there are at most V + 1 passes. Each pass costs at most V checks plus E rule reads:

   (V + 1) × (V + E) steps

   Check it with Example 1: (5 + 1) × (5 + 5) = 60. The real run made 11 checks in 4 passes, because 3 passes were enough to take everything. The worst case is a chain listed backwards, like 4 → 3 → 2 → 1 → 0 swept from 0 up: each pass takes only one course.

4. 4 Keep only the part that grows fastest

   Drop the + 1. What is left is V × (V + E). With 2000 courses and 5000 rules, that is up to 14 million steps: slow, and much worse than needed.

   So the time is O(V × (V + E)).

5. S Space: count the extra memory the same way

   The needs lists hold every rule once: E entries. The taken flags are V. So the space is O(V + E).

   needs lists (E entries)taken flags (V)

Kahn's algorithm O(V + E)

The idea

The brute force rechecks the same waiting courses over and over. Instead, keep a count for each course: how many of its prerequisites are missing. A course is ready exactly when its count is 0.

Put every course with count 0 in a queue. Take courses from the front of the queue. When a course is taken, every course that needs it is missing one less, so lower their counts by 1. A count that drops to 0 means that course is now ready: add it to the queue.

At the end, count the courses taken. If it is all of them, return true.

Why it is correct: a course is taken only when its count is 0, so all its prerequisites were taken before it. A course on a cycle waits for another course on the same cycle, so its count never reaches 0, and it is never taken.

Walkthrough

ready front →

empty

taken

0

1. missing[course] = how many prerequisites course has
2. ready = queue of courses with missing == 0
3. while ready:
4. course = ready.pop_front(); taken += 1
5. for each next_course that needs course:
6. missing[next_course] -= 1
7. if missing[next_course] == 0: ready.push(next_course)
8. return taken == numCourses

Under each course is how many of its prerequisites are still missing. Course 1 needs only 3, course 0 needs 1 and 2.

← BackStep →Play1 / 13

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Kahn's algorithm: count each course's missing prerequisites, and take
    // a course when its count reaches 0. Every course and every rule is handled once.
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> unlocks = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) unlocks.add(new ArrayList<>());
        int[] missing = new int[numCourses];
        for (int[] prerequisite : prerequisites) {
            unlocks.get(prerequisite[1]).add(prerequisite[0]);
            missing[prerequisite[0]]++;
        }
        Deque<Integer> ready = new ArrayDeque<>();
        for (int course = 0; course < numCourses; course++)
            if (missing[course] == 0) ready.add(course);
        int taken = 0;
        while (!ready.isEmpty()) {
            int course = ready.poll();
            taken++;
            for (int nextCourse : unlocks.get(course)) {
                missing[nextCourse]--;
                // Its last missing prerequisite is now taken.
                if (missing[nextCourse] == 0) ready.add(nextCourse);
            }
        }
        // Courses on a cycle never reach 0, so they are never taken.
        return taken == numCourses;
    }
}

Big O

Time O(V + E)Space O(V + E)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Building the lists and counts reads each rule once. Then the while loop pops one course per run, and the inner for follows each arrow out of that course. Popping and following an arrow are fixed jobs, so each is 1 step.

   1. missing[course] = how many prerequisites course has
   2. ready = queue of courses with missing == 0
   3. while ready:
   4. course = ready.pop_front(); taken += 1
   5. for each next_course that needs course:
   6. missing[next_course] -= 1
   7. if missing[next_course] == 0: ready.push(next_course)
   8. return taken == numCourses

2. 2 Count the runs on Example 1

   The table has one column per course, in the order they were taken. Each was popped once, and each followed the arrows out of it.

   5 pops + 2 + 1 + 1 + 1 + 0 = 5 arrows, so 10 steps, after 5 steps to build the counts.

   taken	course 3	course 1	course 2	course 0	course 4
   pops	1	1	1	1	1
   arrows followed	2	1	1	1	0

   total

   5 pops + 5 arrows = 10

3. 3 Write the count for any n

   A course joins the queue once, when its count first hits 0, so it is popped at most once. Its arrows are followed only then, so every arrow is followed at most once:

   E (build) + V (pops) + E (arrows) = V + 2 × E steps

   Check it with Example 1: 5 + 10 = 15 steps. That matches the 5 rules read plus the 10 steps above.

4. 4 Keep only the part that grows fastest

   Drop the 2. What is left is V + E: one look at each course and each rule.

   So the time is O(V + E).

5. S Space: count the extra memory the same way

   The unlocks lists hold every rule once: E entries. The counts and the queue hold at most V each. So the space is O(V + E).

   unlocks lists (E entries)missing counts (V)ready queue (up to V)

Common mistake

Returning true when the queue runs empty

The queue also runs empty when courses are stuck on a cycle: they simply never join it. The answer is the final check, whether the number of courses taken equals numCourses.

Tested at the limits

2,000 random inputs of up to 6 courses and up to 8 different rules, so loops of every length come up. The repeated passes, Kahn's algorithm and a simple loop check written in the test gave the same answer every time.

Largest inputs	Result
2,000 courses and 5,000 rules (the most allowed), with a chain where each course needs the next one. Kahn’s algorithm.	Under 0.01 s, and about 0.2 MB of extra memory: the rule lists and the counts, O(V + E). The same when one rule is turned around to close a loop.
The same 2,000 courses and 5,000 rules. Repeated passes.	0.4 s. The chain lets each pass take only one course, so it needs 2,000 passes over all the rules.