05-Course-Schedule.md

Course Schedule

Problem Link

https://leetcode.com/problems/course-schedule/

---

Pattern

• Topological Sort

---

Approach

Build the prerequisite graph and use Kahn's algorithm to detect whether all courses can be completed.

---

Time Complexity

O(V + E)

Space Complexity

O(V + E)

---

Java Solution

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[] edge : prerequisites) {
            graph.get(edge[1]).add(edge[0]);
            indegree[edge[0]]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) queue.offer(i);
        int visited = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            visited++;
            for (int next : graph.get(course)) {
                if (--indegree[next] == 0) queue.offer(next);
            }
        }
        return visited == numCourses;
    }
}