Course Schedule medium

Problem Statement

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 if you want to take course ai.

For example, the pair [0, 1] means you have to first take course 1 (index 1), before you can take course 0 (index 0).

Determine if it is possible to finish all courses.

Example 1:

  • Input: numCourses = 2, prerequisites = [[1,0]]
  • Output: true
  • Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Example 2:

  • Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
  • Output: false
  • Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Steps to Solve

This problem can be solved using topological sort. Topological sort is an algorithm for ordering elements in a directed acyclic graph (DAG). If a cycle exists (meaning it's not a DAG), a topological sort is impossible, indicating that it's impossible to complete all courses.

  1. Create an adjacency list: Represent the courses and their prerequisites using an adjacency list. This makes it efficient to find the courses that depend on a particular course.

  2. Calculate in-degrees: For each course, count its in-degree (the number of courses that must be completed before it).

  3. Initialize a queue: Add all courses with an in-degree of 0 to a queue. These are the courses with no prerequisites.

  4. Topological sort: While the queue is not empty:

    • Dequeue a course.
    • Decrement the in-degree of all its dependent courses (courses that have it as a prerequisite).
    • If the in-degree of a dependent course becomes 0, add it to the queue.

  5. Check for cycles: If the number of courses processed (visited) equals the total number of courses, then a topological sort was successful, and it's possible to complete all courses. Otherwise, a cycle exists, and it's impossible.

Explanation

The algorithm works by iteratively processing courses with no remaining prerequisites. By removing these courses and updating the prerequisites of their dependents, we effectively simulate taking those courses. If we process all courses, it means there were no cycles. If we get stuck before processing all courses (the queue becomes empty before we process all courses), it signifies a cycle.

Code (Java)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Create adjacency list
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        int[] inDegree = new int[numCourses];
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }

        // Initialize queue with courses having in-degree 0
        Queue<Integer> 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 neighbor : adj.get(course)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        return count == numCourses;
    }
}

Complexity

  • Time Complexity: O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges). This is because we visit each vertex and edge once.
  • Space Complexity: O(V + E) to store the adjacency list and in-degree array. The queue's size will be at most V in the worst case.