40. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first before taking course ai. Return true if you can finish all courses. Otherwise, return false.

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: Circular dependency - impossible.

Problem Breakdown:

1. Build an adjacency list and compute in-degrees for each course. In-degree counts how many prerequisites a course has.

• adj = [[] for _ in range(numCourses)]
  inDegree = [0] * numCourses
  for course, prereq in prerequisites:
      adj[prereq].append(course)
      inDegree[course] += 1

2. Initialize a queue with all courses that have in-degree 0 (no prerequisites). These can be taken immediately.

• from collections import deque
  queue = deque()
  for i in range(numCourses):
      if inDegree[i] == 0:
          queue.append(i)

3. Process courses from the queue (BFS/topological sort). For each completed course, reduce in-degrees of dependent courses. If a dependent course reaches in-degree 0, add it to the queue.

• count = 0
  while queue:
      course = queue.popleft()
      count += 1
      for next_course in adj[course]:
          inDegree[next_course] -= 1
          if inDegree[next_course] == 0:
              queue.append(next_course)

4. If we processed all courses (count == numCourses), there is no cycle and all courses can be completed. Otherwise, a cycle exists.

• return count == numCourses

Summary:

Use topological sort (Kahn's algorithm). Build a graph and track in-degrees. Start with courses having no prerequisites. Process them, reducing in-degrees of dependents. If all courses are processed, no cycle exists.

Time and Space Complexity:

Time Complexity: O(V + E) - where V is the number of courses and E is the number of prerequisites.

Space Complexity: O(V + E) - for the adjacency list and in-degree array.

Python Solution:

def canFinish(numCourses, prerequisites):
    from collections import deque
    adj = [[] for _ in range(numCourses)]
    inDegree = [0] * numCourses
    for course, prereq in prerequisites:
        adj[prereq].append(course)
        inDegree[course] += 1
    queue = deque()
    for i in range(numCourses):
        if inDegree[i] == 0:
            queue.append(i)
    count = 0
    while queue:
        course = queue.popleft()
        count += 1
        for next_course in adj[course]:
            inDegree[next_course] -= 1
            if inDegree[next_course] == 0:
                queue.append(next_course)
    return count == numCourses

JavaScript Solution:

var canFinish = function(numCourses, prerequisites) {
    const adj = Array.from({ length: numCourses }, () => []);
    const inDegree = new Array(numCourses).fill(0);
    for (const [course, prereq] of prerequisites) {
        adj[prereq].push(course);
        inDegree[course]++;
    }
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (inDegree[i] === 0) queue.push(i);
    }
    let count = 0;
    while (queue.length > 0) {
        const course = queue.shift();
        count++;
        for (const next of adj[course]) {
            inDegree[next]--;
            if (inDegree[next] === 0) queue.push(next);
        }
    }
    return count === numCourses;
};

Java Solution:

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List> adj = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }
        Queue queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++)
            if (inDegree[i] == 0) queue.offer(i);
        int count = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;
            for (int next : adj.get(course)) {
                inDegree[next]--;
                if (inDegree[next] == 0) queue.offer(next);
            }
        }
        return count == numCourses;
    }
}