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] indicates that to take course 0 you have to first take course 1.

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

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

1. Build the graph: Represent the courses and prerequisites as a directed graph. Each course is a node, and a prerequisite [a, b] represents a directed edge from b to a (because you must take b before a). We'll use an adjacency list for efficient representation.

2. Detect cycles: A cycle in the graph indicates that there's a circular dependency between courses, making it impossible to finish all courses. We'll use Depth-First Search (DFS) with a visited array and a recursion stack to detect cycles.

3. Topological Sort (Optional): While cycle detection is sufficient, you could also perform a topological sort as a secondary check. If a topological sort is possible, it means there are no cycles, and all courses can be completed.

Explanation

The core idea is to check for cycles in the directed graph representing course dependencies. A cycle means you'll never be able to finish all courses because you'll always need to take a course that requires itself (directly or indirectly). DFS is an efficient way to detect cycles in a graph.

The visited array keeps track of visited nodes. The recursionStack keeps track of nodes currently in the recursion path. If we encounter a node already in the recursionStack, it indicates a cycle.

Code

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    // Build the graph (adjacency list)
    const graph: number[][] = Array.from({ length: numCourses }, () => []);
    const inDegree: number[] = Array(numCourses).fill(0); //Keeps track of incoming edges for each node

    for (const [course, pre] of prerequisites) {
        graph[pre].push(course);
        inDegree[course]++;
    }

    // Find nodes with no incoming edges (starting points)
    const queue: number[] = [];
    for (let i = 0; i < numCourses; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }

    let count = 0; // Count of processed nodes

    while (queue.length > 0) {
        const course = queue.shift()!;
        count++;

        for (const neighbor of graph[course]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) {
                queue.push(neighbor);
            }
        }
    }

    return count === numCourses; //If all nodes were processed, then there is no cycle
};

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 traverse the graph once using BFS.
• Space Complexity: O(V + E) to store the graph (adjacency list) and the queue. In the worst case, the queue could contain all vertices.