Course Schedule

Medium Problem 106 of 151 Java and Python

Problem

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

Return true if you can finish all courses, otherwise false.

Example 1

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

Example 2

Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
Why: Each course needs the other first: a cycle.

Constraints

1 ≤ numCourses ≤ 2000
0 ≤ prerequisites.length ≤ 5000; all pairs are unique.

Explanation

Draw an edge b → a for each prerequisite. You can finish everything exactly when this directed graph has no cycle.

Kahn's algorithm finds out: repeatedly take a course with no remaining prerequisites (in-degree 0), and "complete" it by lowering the in-degree of courses that depend on it. If every course gets taken, there was no cycle.

Approach 1 · Better

DFS cycle detection with three colours

Time O(V + E)
Space O(V + E)

DFS the graph, colouring nodes white (unvisited), grey (on the current path) and black (finished). Reaching a grey node again means a cycle.

Build the adjacency list b → a.
dfs(node): mark grey; for each next node, a grey neighbour means a cycle; recurse into white ones; mark black.
Return false if any DFS finds a cycle.

Java

import java.util.*;

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<>());
        }
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
        }
        int[] state = new int[numCourses]; // 0 white, 1 grey, 2 black
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(graph, i, state)) {
                return false;
            }
        }
        return true;
    }

    private boolean hasCycle(List<List<Integer>> graph, int node, int[] state) {
        if (state[node] == 1) {
            return true;
        }
        if (state[node] == 2) {
            return false;
        }
        state[node] = 1;
        for (int next : graph.get(node)) {
            if (hasCycle(graph, next, state)) {
                return true;
            }
        }
        state[node] = 2;
        return false;
    }
}

Python

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[b].append(a)
        state = [0] * numCourses  # 0 white, 1 grey, 2 black

        def has_cycle(node):
            if state[node] == 1:
                return True
            if state[node] == 2:
                return False
            state[node] = 1
            if any(has_cycle(nxt) for nxt in graph[node]):
                return True
            state[node] = 2
            return False

        return not any(has_cycle(i) for i in range(numCourses))

Approach 2 · Optimal

Kahn's algorithm (BFS topological sort)

Time O(V + E)
Space O(V + E)

Count prerequisites (in-degree) per course. Start with courses that have none; taking a course lowers its dependants' in-degree. Count how many courses you manage to take.

Build the graph and in-degree array.
Queue every course with in-degree 0.
Pop a course, count it, and decrement each dependant's in-degree, queuing those that reach 0.
Return taken == numCourses.

Java

import java.util.*;

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]);
            inDegree[p[0]]++;
        }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        int taken = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            taken++;
            for (int next : graph.get(course)) {
                if (--inDegree[next] == 0) {
                    queue.add(next);
                }
            }
        }
        return taken == numCourses;
    }
}

Python

from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)
            in_degree[a] += 1
        queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
        taken = 0
        while queue:
            course = queue.popleft()
            taken += 1
            for nxt in graph[course]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    queue.append(nxt)
        return taken == numCourses

Complexity compared

Approach	Time	Space
Better DFS cycle detection with three colours	O(V + E)	O(V + E)
Optimal Kahn's algorithm (BFS topological sort)	O(V + E)	O(V + E)

Key takeaways

"Can all tasks with dependencies be completed?" = "is the directed graph acyclic?"
Two colours are not enough for directed graphs: you need grey (on the current path) to tell a cycle from a shared descendant.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem