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 = 2, prerequisites = [[1,0]]

Output: [0,1]

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2

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

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

Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Steps

1. Build the graph: Create an adjacency list to represent the course dependencies. Each course will be a node, and an edge from course b to course a indicates that b is a prerequisite for a.
2. Calculate in-degrees: For each course, count its in-degree (the number of prerequisites it has).
3. Find starting nodes: Add all courses with an in-degree of 0 to a queue. These are the courses with no prerequisites.
4. Topological sort: Iteratively process courses from the queue. For each course:
   • Add it to the result list.
   • Decrement the in-degree of its neighbors (courses that depend on it).
   • If a neighbor's in-degree becomes 0, add it to the queue.
5. Check for cycles: If the length of the result list is not equal to numCourses, it means there's a cycle in the graph, and it's impossible to finish all courses. Return an empty array in this case.

Explanation

The algorithm uses topological sort to find a valid course order. Topological sort is an algorithm for ordering the nodes in a directed acyclic graph (DAG) such that for every directed edge from node A to node B, node A appears before node B in the ordering. If a cycle exists (a directed path that starts and ends at the same node), topological sort is not possible, indicating that it's impossible to complete all courses.

The algorithm efficiently handles this by tracking in-degrees. By only processing nodes with an in-degree of 0, we ensure that we always process prerequisites before the courses that depend on them.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        List<int>[] graph = new List<int>[numCourses];
        int[] inDegree = new int[numCourses];

        // Build the graph and calculate in-degrees
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new List<int>();
        }
        foreach (int[] pre in prerequisites) {
            graph[pre[1]].Add(pre[0]);
            inDegree[pre[0]]++;
        }

        Queue<int> queue = new Queue<int>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.Enqueue(i);
            }
        }

        List<int> result = new List<int>();
        while (queue.Count > 0) {
            int course = queue.Dequeue();
            result.Add(course);
            foreach (int neighbor in graph[course]) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.Enqueue(neighbor);
                }
            }
        }

        if (result.Count == numCourses) {
            return result.ToArray();
        } else {
            return new int[0]; // Cycle detected
        }
    }
}

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 graph and the in-degree array. The queue's size is at most V in the worst case.