LeetCode 207. Course Schedule

Posted on Edited on In , Views:

🧩 Problem Description

There are numCourses courses labeled from 0 to numCourses - 1.
You are given an array prerequisites where prerequisites[i] = [a, b] indicates that to take course a you must first take course b.

Return true if you can finish all courses. Otherwise, return false.

This is essentially asking whether the directed graph has a cycle. If there is no cycle, a topological ordering exists and you can finish all courses.

💬 Examples

Example 1

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

Example 2

1
2
3
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 0 depends on 1 and 1 depends on 0 → cycle.

💡 Approach 1: Kahn’s Algorithm (BFS Topological Sort)

  • Build adjacency list and in-degree array.
  • Push all nodes with in-degree 0 into a queue.
  • Pop from queue, decrement in-degree of neighbors, and push any that drop to 0.
  • If we process all nodes, there is no cycle; otherwise, a cycle exists.

🔢 Java Code (BFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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[] indeg = new int[numCourses];
        for (int[] p : prerequisites) {
            int a = p[0], b = p[1];
            graph.get(b).add(a);
            indeg[a]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);

        int taken = 0;
        while (!q.isEmpty()) {
            int cur = q.poll();
            taken++;
            for (int nxt : graph.get(cur)) {
                if (--indeg[nxt] == 0) q.offer(nxt);
            }
        }
        return taken == numCourses;
    }
}

💡 Approach 2: DFS Cycle Detection (3-color / visiting states)

  • Maintain a state[] array: 0 = unvisited, 1 = visiting, 2 = visited.
  • During DFS, if we reach a node marked visiting (1), we found a cycle.
  • If DFS finishes without back edges, there is no cycle.

🔢 Java Code (DFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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];
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0 && hasCycle(i, graph, state)) return false;
        }
        return true;
    }

    private boolean hasCycle(int u, List<List<Integer>> g, int[] state) {
        state[u] = 1; // visiting
        for (int v : g.get(u)) {
            if (state[v] == 1) return true;           // back edge
            if (state[v] == 0 && hasCycle(v, g, state)) return true;
        }
        state[u] = 2; // visited
        return false;
    }
}

⏱ Time and Space Complexity

  • BFS (Kahn):
    • Time: O(V + E)
    • Space: O(V + E) for graph + queue + indegree
  • DFS:
    • Time: O(V + E)
    • Space: O(V + E) for graph + recursion stack

V = numCourses, E = len(prerequisites).

✍️ Summary

  • The problem reduces to cycle detection in a directed graph.
  • Kahn (BFS) is usually simplest when you just need a yes/no; it also gives a topo order.
  • DFS 3-color is elegant and stack-based.
  • Pick based on your preference and constraints.

Related problems

  • lc-210 — Course Schedule II (return topological order)
  • lc-261 — Graph Valid Tree (undirected)
  • lc-802 — Find Eventual Safe States