Course Schedule II 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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output: [0,2,1,3] or [0,1,2,3]

Explanation: There are a total of 4 courses to take. To take course 1 you should have finished course 0, and to take course 2 you should also have finished course 0. Finally, to take course 3 you should have finished both courses 1 and 2. Both the output sequences are valid.

Example 2:

Input: numCourses = 1, prerequisites = []

Output: [0]

Explanation: Just one course to take '0'.

Steps to Solve

1. Build the Graph: Represent the courses and prerequisites as a directed graph. Each course is a node, and a prerequisite [ai, bi] represents a directed edge from bi to ai (you must take bi before ai).

2. Find In-degrees: Calculate the in-degree of each node (the number of incoming edges). This represents how many courses must be completed before this course can be taken.

3. Topological Sort: Use a topological sort algorithm (e.g., Kahn's algorithm) to find a valid course order. This algorithm iteratively removes nodes with an in-degree of 0 (courses with no prerequisites) and updates the in-degrees of their neighbors.

4. Handle Cycles: If a cycle is detected (meaning you can't find a node with in-degree 0), it's impossible to complete all courses, so return an empty array.

Explanation

Kahn's algorithm works by prioritizing nodes with no incoming edges. We maintain a queue of such nodes. We repeatedly remove a node from the queue, add it to the result, and decrement the in-degrees of its neighbors. If at any point the queue becomes empty and there are still nodes with non-zero in-degrees, it means a cycle exists.

Code (Typescript)

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
    // 1. Build the graph (adjacency list) and calculate in-degrees
    const graph: number[][] = Array.from({ length: numCourses }, () => []);
    const inDegrees: number[] = new Array(numCourses).fill(0);

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

    // 2. Topological sort using Kahn's algorithm
    const queue: number[] = [];
    const result: number[] = [];

    for (let i = 0; i < numCourses; i++) {
        if (inDegrees[i] === 0) {
            queue.push(i);
        }
    }

    while (queue.length > 0) {
        const course = queue.shift()!;
        result.push(course);

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

    // 3. Check for cycles
    if (result.length !== numCourses) {
        return []; // Cycle detected
    }

    return result;
}

Complexity

• Time Complexity: O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges). This is due to the graph traversal and topological sort.

• Space Complexity: O(V + E) to store the graph and in-degrees. The queue and result array also take at most O(V) space.