207. Course Schedule

Description

Determine if it is possible to finish all courses given the number of courses and the prerequisites for each course. Each course is labeled from 0 to numCourses - 1. You are given a list of prerequisite pairs, where prerequisites[i] = [ai, bi] indicates that you must take course bi before course ai.

Intuition

The problem can be reduced to detecting if there is a cycle in a directed graph. If there is a cycle, it's impossible to complete all courses. We use topological sorting (Kahn's algorithm) to detect cycles and determine the order of courses.

Approach

1. Graph Representation: - Use an adjacency matrix to represent the graph. - Use an array to keep track of the number of prerequisites each course has.
2. Topological Sorting: - Initialize a queue to store courses with no prerequisites. - Use BFS to process each course, decrementing the prerequisite count of connected courses. - Add courses with no remaining prerequisites to the queue.
3. Cycle Detection: - If the number of processed courses equals numCourses, all courses can be finished. - If not, there is a cycle in the graph, making it impossible to finish all courses.

Complexity

Time Complexity:

• Constructing the graph takes O(P) time, where P is the number of prerequisites.
• Topological sorting takes O(V + E) time, where V is the number of courses and E is the number of prerequisites.
• Total time complexity is O(V + P).

Space Complexity:

• The adjacency matrix takes O(V^2) space.
• The requirements array takes O(V) space.
• The queue takes up to O(V) space.
• Total space complexity is O(V^2).

Code

C++

class Solution {
public:
    bool canFinish(int numCourses, vector>& prerequisites) {
        if (numCourses <= 1 || prerequisites.empty()) {
            return true;
        }
        vector> matrix(numCourses, vector(numCourses, 0));
        vector requirements(numCourses, 0);

        for (const auto& each : prerequisites) {
            int course = each[0];
            int pre = each[1];
            if (matrix[pre][course] == 0) {
                requirements[course]++;
            }
            matrix[pre][course] = 1;
        }
        queue stack;
        for (int i = 0; i < numCourses; ++i) {
            if (requirements[i] == 0) {
                stack.push(i);
            }
        }
        int counter = 0;
        while (!stack.empty()) {
            int course = stack.front();
            stack.pop();
            counter++;
            for (int i = 0; i < numCourses; ++i) {
                if (matrix[course][i] != 0) {
                    requirements[i]--;
                    if (requirements[i] == 0) {
                        stack.push(i);
                    }
                }
            }
        }
        return counter == numCourses;
    }
};

Python

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        if numCourses <= 1 or not prerequisites:
            return True

        matrix = [[0] * numCourses for _ in range(numCourses)]
        requirements = [0] * numCourses

        for course, pre in prerequisites:
            if matrix[pre][course] == 0:
                requirements[course] += 1
            matrix[pre][course] = 1

        stack = [i for i in range(numCourses) if requirements[i] == 0]
        counter = 0
        while stack:
            course = stack.pop(0)
            counter += 1
            for i in range(numCourses):
                if matrix[course][i] != 0:
                    requirements[i] -= 1
                    if requirements[i] == 0:
                        stack.append(i)

        return counter == numCourses

Java

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 1 || prerequisites == null || prerequisites.length <= 1) {
            return true;
        }
        int[][] matrix = new int[numCourses][numCourses];
        int[] requirements = new int[numCourses];

        for (int[] each : prerequisites) {
            int course = each[0];
            int pre = each[1];
            if (matrix[pre][course] == 0) {
                requirements[course]++;
            }
            matrix[pre][course] = 1;
        }
        java.util.Queue stack = new java.util.LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (requirements[i] == 0) {
                stack.add(i);
            }
        }
        int counter = 0;
        while (!stack.isEmpty()) {
            int course = stack.poll();
            counter++;
            for (int i = 0; i < numCourses; i++) {
                if (matrix[course][i] != 0) {
                    requirements[i]--;
                    if (requirements[i] == 0) {
                        stack.add(i);
                    }
                }
            }
        }
        return counter == numCourses;
    }
}

JavaScript

var canFinish = function (numCourses, prerequisites) {
    if (numCourses <= 1 || !prerequisites || prerequisites.length <= 1) {
        return true;
    }
    const matrix = Array.from({ length: numCourses }, () => new Array(numCourses).fill(0));
    const requirements = new Array(numCourses).fill(0);
    prerequisites.forEach(each => {
        const [course, pre] = each;
        if (matrix[pre][course] === 0) {
            requirements[course]++;
        }
        matrix[pre][course] = 1;
    });
    const stack = [];
    requirements.forEach((each, index) => {
        if (each === 0) {
            stack.push(index);
        }
    });
    let counter = 0;
    while (stack.length) {
        const course = stack.shift();
        counter++;
        for (let i = 0; i < numCourses; i++) {
            if (matrix[course][i] !== 0) {
                requirements[i]--;
                if (requirements[i] === 0) {
                    stack.push(i);
                }
            }
        }
    }
    return counter === numCourses;
};