Course Schedule

Medium Graphs Topological Sort Original on LeetCode

Course Schedule is a medium graphs problem solved with the topological sort pattern. The best approach, kahn's algorithm, runs in O(V + E) time and O(V + E) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from dfs cycle detection up.

Problem

There are numCourses courses. Each pair [a, b] in prerequisites means you must take course b before course a. Decide whether it is possible to finish every course.

Examples

Example 1

Input
numCourses = 3, prerequisites = [[1,0],[2,1]]
Output
true
Why
Take 0, then 1, then 2.

Example 2

Input
numCourses = 2, prerequisites = [[1,0],[0,1]]
Output
false

Constraints

  • 1 <= numCourses <= 2000; [a, b] means b must be taken before a.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
DFS cycle detectionO(V + E)O(V + E)
Kahn's algorithmO(V + E)O(V + E)

1DFS cycle detection

TimeO(V + E)
SpaceO(V + E)

Build edges b → a and look for a back edge with three-state DFS.

  1. state 0/1/2; an edge into a state-1 node means a cycle, so return false.
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);
        int[] state = new int[numCourses];
        for (int i = 0; i < numCourses; i++) if (state[i] == 0 && cyclic(i, adj, state)) return false;
        return true;
    }

    private boolean cyclic(int u, List<List<Integer>> adj, int[] state) {
        state[u] = 1;
        for (int v : adj.get(u)) {
            if (state[v] == 1) return true;
            if (state[v] == 0 && cyclic(v, adj, state)) return true;
        }
        state[u] = 2;
        return false;
    }
}

2Kahn's algorithm

TimeO(V + E)
SpaceO(V + E)

Take courses with no remaining prerequisites first. Each course taken lowers its dependants' in-degree. If every course gets taken, there is no cycle.

  1. indeg from edges b → a; queue zeros.
  2. Pop, taken++, decrement neighbours.
  3. Return taken == numCourses.
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (int[] p : prerequisites) { adj.get(p[1]).add(p[0]); indeg[p[0]]++; }
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.add(i);
        int taken = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            taken++;
            for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
        }
        return taken == numCourses;
    }
}

Edge cases to test

  • No prerequisites
  • A course that requires itself

Hints

Hint 1

You can finish every course exactly when the prerequisite graph has no cycle.

FAQ

What is the best time complexity for Course Schedule?

Kahn's algorithm runs in O(V + E) time and O(V + E) extra space.

Which pattern does Course Schedule use?

It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule II, Alien Dictionary.

Is there a brute force solution for Course Schedule?

Yes. DFS cycle detection takes O(V + E) time and O(V + E) space. Build edges b → a and look for a back edge with three-state DFS.

Which edge cases should I test for Course Schedule?

No prerequisites; A course that requires itself.