87.Course Schedule

MediumBlind 75Graphs · 8/19

Problem

There are numCourses courses labelled 0 to numCourses - 1. You are given prerequisites, where prerequisites[i] = [a, b] means you must take course b before course a.

Return true if it is possible to finish all courses, otherwise false.

Examples

Input:  numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: Take course 0, then course 1.

Input:  numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: Course 1 needs 0 and course 0 needs 1 — a cycle, so neither can ever be taken.

Input:  numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: true
Explanation: One valid order is 0, 1, 2, 3.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a, b < numCourses
All pairs prerequisites[i] are unique

💡 Key Insight

Model courses as nodes and each pair [a, b] as a directed edge b → a. All courses can be finished if and only if this directed graph has no cycle — a cycle means every course in it waits on another course in it. Cycle detection in a directed graph takes O(V + E) with either DFS three-colouring (a back edge to a node "in progress" is a cycle) or Kahn's algorithm (repeatedly remove nodes with in-degree 0; if some remain, they sit on a cycle).

Brute Force (Repeated Elimination Rounds)

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

Intuition

Simulate semesters. In each round, take every course whose prerequisites have all already been taken. If a round makes no progress while courses remain, the remaining courses wait on each other forever. Each round rescans every prerequisite pair, which is where the extra factor of V comes from.

Algorithm

taken[] all false, count = 0.
Repeat:
- Mark blocked[a] = true for every pair [a, b] where b is not yet taken.
- Take every course that is neither taken nor blocked; increment count.
- If nothing was taken this round, stop.
Return count == numCourses.

Visualization

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

round 1: blocked = {1,2,3} → take {0}        count = 1
round 2: blocked = {3}     → take {1,2}      count = 3
round 3: blocked = {}      → take {3}        count = 4
round 4: nothing left      → stop            4 == 4 → true

With [[1,0],[0,1]]: round 1 blocked = {0,1} → nothing taken → false

Code

java

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        boolean[] taken = new boolean[numCourses];
        int count = 0;

        while (true) {
            // A course is blocked if any of its prerequisites is not yet taken
            boolean[] blocked = new boolean[numCourses];
            for (int[] p : prerequisites) {
                if (!taken[p[1]]) blocked[p[0]] = true;
            }
            boolean progress = false;
            for (int course = 0; course < numCourses; course++) {
                if (!taken[course] && !blocked[course]) {
                    taken[course] = true;
                    count++;
                    progress = true;
                }
            }
            if (!progress) break; // no course is available this round
        }
        return count == numCourses;
    }
}

Complexity

Time: O(V·(V + E)) — up to V rounds (a chain of courses), each scanning all E pairs and V courses.
Space: O(V) — the taken and blocked arrays.

DFS Cycle Detection (Three Colours)

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

Intuition

Run DFS along b → a edges and colour each node: 0 = unvisited, 1 = on the current DFS path, 2 = fully explored and known to be cycle-free. Reaching a node coloured 1 means we came back to a node on our own path — a cycle. Nodes coloured 2 are skipped, so each node and edge is explored only once.

Algorithm

Build adjacency lists graph[b].add(a) for every [a, b].
For each course with state 0, call hasCycle(course); if it returns true, return false.
hasCycle(u): if state[u] == 1 return true; if state[u] == 2 return false. Set state[u] = 1, recurse into all neighbours, then set state[u] = 2 and return false.
Return true.

Dry Run

flowchart LR
    C0["course 0<br/>state 1"] -->|"edge 0 to 1"| C1["course 1<br/>state 1"]
    C1 -->|"edge 1 to 0"| C0b{"course 0 has state 1?"}
    C0b -->|"yes: back edge"| R["cycle found<br/>return false"]

For [[1,0],[0,1]]: DFS starts at 0 (state 1), follows 0 → 1 (state 1), then 1 → 0 finds 0 still on the path.

Code

java

import java.util.ArrayList;
import java.util.List;

class Solution {
    private List<List<Integer>> graph;
    private int[] state; // 0 = unvisited, 1 = visiting, 2 = done

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]); // edge: prerequisite -> course
        }
        state = new int[numCourses];
        for (int course = 0; course < numCourses; course++) {
            if (state[course] == 0 && hasCycle(course)) return false;
        }
        return true;
    }

    private boolean hasCycle(int u) {
        if (state[u] == 1) return true;  // back edge to the current path
        if (state[u] == 2) return false; // already proven cycle-free
        state[u] = 1;
        for (int next : graph.get(u)) {
            if (hasCycle(next)) return true;
        }
        state[u] = 2;
        return false;
    }
}

Complexity

Time: O(V + E) — every node is coloured once and every edge is followed once.
Space: O(V + E) — adjacency lists, plus state and the recursion stack up to depth V.

Kahn's Topological SortOptimal

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

Intuition

A course with in-degree 0 has no unmet prerequisites, so it can be taken now. Take it, and "remove" its outgoing edges by decrementing the in-degree of each course that depended on it; any course whose in-degree drops to 0 becomes available. Unlike the brute force, we never rescan — a queue holds exactly the available courses. If a cycle exists, its courses never reach in-degree 0, so fewer than numCourses courses are processed.

Algorithm

Build graph[b].add(a) and indegree[a]++ for each [a, b].
Enqueue every course with indegree == 0.
While the queue is non-empty: pop u, taken++; for each v in graph[u], decrement indegree[v] and enqueue v if it reached 0.
Return taken == numCourses.

Dry Run

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]] → in-degrees 0:0, 1:1, 2:1, 3:2.

flowchart TD
    S["queue [0]<br/>indegree 0:0 1:1 2:1 3:2"] --> A["pop 0, taken = 1<br/>1 and 2 drop to 0<br/>queue [1, 2]"]
    A --> B["pop 1, taken = 2<br/>3 drops to 1"]
    B --> C["pop 2, taken = 3<br/>3 drops to 0<br/>queue [3]"]
    C --> D["pop 3, taken = 4"]
    D --> E{"taken == 4?"}
    E -->|"yes"| F["return true"]

Code

java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        int[] indegree = new int[numCourses];
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]); // prerequisite -> course
            indegree[p[0]]++;
        }

        // Courses with no prerequisites can be taken immediately
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }

        int taken = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            taken++;
            for (int v : graph.get(u)) {
                if (--indegree[v] == 0) queue.offer(v); // all of v's prerequisites done
            }
        }
        return taken == numCourses; // leftovers are stuck in a cycle
    }
}

Complexity

Time: O(V + E) — each course is enqueued once and each edge decrements one in-degree once.
Space: O(V + E) — adjacency lists, indegree and the queue.

Complexity Comparison

Approach	Time	Space
Repeated Elimination Rounds	O(V·(V + E))	O(V)
DFS (Three Colours)	O(V + E)	O(V + E)
Kahn's Topological Sort	O(V + E)	O(V + E)

Common Pitfalls

Using a single visited boolean for DFS — it cannot distinguish "on the current path" (cycle) from "finished earlier via another branch" (fine), so diamonds like 0→1→3, 0→2→3 get reported as cycles.
Forgetting to set the state to "done" after exploring a node, which makes the DFS exponential on dense DAGs.
Reversing the edge direction inconsistently — for cycle detection either direction works, but building graph[a].add(b) while counting indegree[a] breaks Kahn's algorithm.
Assuming every course appears in prerequisites; courses with no pairs at all have in-degree 0 and must still be counted.
Starting DFS only from course 0 — the graph may be disconnected, so every unvisited course must be a starting point.