Course Schedule

NeetCode: Course Schedule · LeetCode: 207. Course Schedule · Difficulty: Medium

There are numCourses courses labeled 0 to numCourses - 1. Each pair [a, b] means you must take course b before course a. Return true if you can finish all courses.

Example

Text

numCourses = 2, prerequisites = [[1,0]]         Output: true
numCourses = 2, prerequisites = [[1,0],[0,1]]   Output: false

Model each pair as a directed edge b -> a ("b unlocks a"). All courses can be finished exactly when this graph has no cycle: a cycle is a set of courses each waiting for the next.

Brute force: try to walk from every course back to itself

A cycle exists if and only if some node can reach itself. So for every course s, search from s's successors and see whether s shows up. Each search needs a fresh visited array. The adjacency list is a List<List<Integer>>, so adj.get(b) holds the courses that b unlocks.

Java

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

public class Main {
    static class Solution {
        private boolean reaches(List<List<Integer>> adj, int from, int target, boolean[] visited) {
            if (from == target) {
                return true;
            }
            if (visited[from]) {
                return false;
            }
            visited[from] = true;
            for (int next : adj.get(from)) {
                if (reaches(adj, next, target, visited)) {
                    return true;
                }
            }
            return false;
        }

        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]);
            }
            for (int s = 0; s < numCourses; s++) {
                boolean[] visited = new boolean[numCourses];
                for (int next : adj.get(s)) {
                    if (reaches(adj, next, s, visited)) {
                        return false;
                    }
                }
            }
            return true;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.canFinish(2, new int[][]{{1, 0}}));
        System.out.println(s.canFinish(2, new int[][]{{1, 0}, {0, 1}}));
        System.out.println(s.canFinish(1, new int[][]{}));
        System.out.println(s.canFinish(3, new int[][]{{1, 0}, {2, 1}, {0, 2}}));
    }
}

Output

true
false
true
false

Time: O(V * (V + E)), one full search per course. Space: O(V + E), including the recursion depth of up to V.

Optimal: Kahn's topological sort

Count each course's indegree (how many prerequisites it still waits for). Courses with indegree 0 can be taken now: queue them. Taking a course removes its outgoing edges, so decrement its successors' indegrees and queue any that reach 0. If all V courses get taken, there is no cycle; if the queue drains earlier, the remaining courses lie on or behind a cycle.

Java

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

public class Main {
    static 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[] indegree = new int[numCourses];
            for (int[] p : prerequisites) {
                adj.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 : adj.get(course)) {
                    indegree[next]--;
                    if (indegree[next] == 0) {
                        queue.add(next);
                    }
                }
            }
            return taken == numCourses;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.canFinish(2, new int[][]{{1, 0}}));
        System.out.println(s.canFinish(2, new int[][]{{1, 0}, {0, 1}}));
        System.out.println(s.canFinish(1, new int[][]{}));
        System.out.println(s.canFinish(3, new int[][]{{1, 0}, {2, 1}, {0, 2}}));
    }
}

Output

true
false
true
false

indegree[next]-- never goes below zero: next was counted once per incoming edge, and each edge is processed once. ArrayDeque is the queue here: add inserts at the tail and poll removes from the head. Time: O(V + E). Space: O(V + E).