Start practising

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, 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.

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 Java code.

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.
Java
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.
Java
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.