Course Schedule II

Problem Statement

The task is to determine a valid sequence of courses based on given prerequisites. Each course is identified by a unique integer ranging from 0 to numCourses - 1. The prerequisites array contains pairs such that the second element in each pair must be completed before the first element can be taken. These prerequisites directly influence the valid order in which courses can be undertaken, constructing a dependency sequence. The problem requires finding an order of course completion that satisfies all the given dependencies. If a valid order exists, return any one of them; if it's not possible to complete all courses (due to circular dependencies or other issues), then an empty array should be returned.

Examples

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,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].

Example 3

Input:

numCourses = 1, prerequisites = []

Output:

[0]

Constraints

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• ai != bi
• All the pairs [ai, bi] are distinct.

Approach and Intuition

To solve this problem, a typical approach involves using graph theory, specifically a technique known as topological sorting. Each course can be represented as a node in a graph, and each prerequisite pair as a directed edge from one node to another. The goal is to produce any topological ordering of the courses that respects the direction of edges.

1. Representation: Convert the list of prerequisites into an adjacency list, representing the directed edges from pre-required courses to consequent courses.
2. Initialization: Start with courses that have no prerequisites. These courses can be initially added to the solution.
3. Processing: Utilize a queue to manage the courses as they are processed. Begin with courses that have no prerequisites.
4. Cycle Detection: If during processing we end up revisiting a course that's only partially processed (indicating a cycle), it's concluded that it's impossible to complete all courses. In such a case, return an empty array.
5. Order Construction: For each node/course processed from the queue, append it to the result array and reduce the in-degree of its neighboring nodes by one. If any neighbor’s in-degree drops to zero, it gets added to the queue indicating it has no further prerequisites remaining and is ready to be processed.

By the end of this process, if we've successfully processed all courses, the resultant array provides a valid order. If not all courses are processed (due to remaining courses having non-zero in-degree after processing, indicating cycles or unresolvable dependencies), it would mean that no valid ordering exists, thereby returning an empty array.

This approach efficiently maps out the problem using graph traversal techniques, ensuring that all constraints and prerequisites are appropriately considered. The method is computationally feasible within the given constraints, managing to find a solution or establish the impossibility of one in reasonable time.

Solutions

class Solution {
public:
    vector<int> sortCourses(int totalCourses, vector<vector<int>>& deps) {
        map<int, list<int>> graph;
        vector<int> inDegrees(totalCourses, 0);
        vector<int> courseOrder;
    
        // Building the graph
        for (const auto& dep : deps) {
            int course = dep[0];
            int prerequisite = dep[1];
            graph[prerequisite].push_back(course);
            inDegrees[course]++;
        }
    
        // Queue for courses with no prerequisites
        queue<int> coursesQueue;
        for (int i = 0; i < totalCourses; i++) {
            if (inDegrees[i] == 0) {
                coursesQueue.push(i);
            }
        }
    
        // Processing the graph
        while (!coursesQueue.empty()) {
            int currentCourse = coursesQueue.front();
            coursesQueue.pop();
            courseOrder.push_back(currentCourse);
    
            if (graph.count(currentCourse)) {
                for (int neighbor : graph[currentCourse]) {
                    inDegrees[neighbor]--;
                    if (inDegrees[neighbor] == 0) {
                        coursesQueue.push(neighbor);
                    }
                }
            }
        }
    
        // Check if we could sort all courses
        if (courseOrder.size() == totalCourses) {
            return courseOrder;
        }
    
        return vector<int>();
    }
};