algoadvance

Leetcode 210. Course Schedule II

Problem Statement

You are given a total of numCourses courses labeled from 0 to numCourses-1. You are also given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi before 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.

Clarifying Questions

1. Q: Can there be duplicate pairs in the prerequisites? A: No, each pair [ai, bi] is unique and indicates one specific prerequisite relationship.

2. Q: Can the courses have no prerequisites? A: Yes, some courses can have no prerequisites, and you can take them anytime.

3. Q: What should be returned if it’s impossible to complete all courses? A: An empty array should be returned.

Code

Here’s the C++ solution using Kahn’s Algorithm (Breadth-First Search) for Topological Sorting of a Directed Acyclic Graph (DAG):

#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // Initialize graph and in-degree count
        vector<vector<int>> graph(numCourses);
        vector<int> inDegree(numCourses, 0);
        
        // Build the graph
        for (const auto& pair : prerequisites) {
            int course = pair[0];
            int prerequisite = pair[1];
            graph[prerequisite].push_back(course);
            inDegree[course]++;
        }
        
        // Find all starting points (nodes with in-degree 0)
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        // Perform the topological sort
        vector<int> order;
        while (!q.empty()) {
            int current = q.front();
            q.pop();
            order.push_back(current);
            for (int neighbor : graph[current]) {
                if (--inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        // Check if topological sort is possible
        if (order.size() != numCourses) {
            return {};
        }
        
        return order;
    }
};

Strategy

1. Graph Construction: Build the graph using adjacency lists and calculate the in-degrees of all nodes.
2. Queue Initialization: Initialize a queue with all nodes that have an in-degree of 0 (i.e., courses with no prerequisites).
3. Topological Sort: Perform BFS to generate a topological ordering:
   • Remove a node from the queue.
   • Add it to the result list.
   • Decrease the in-degree of all its neighbors.
   • If any neighbor’s in-degree becomes 0, add it to the queue.
4. Check for Cycles: If the result list’s size is less than numCourses, a cycle exists so it’s impossible to complete all courses; return an empty array in that case.

Time Complexity

• Graph Building: O(E), where E is the number of edges (prerequisites).
• Queue Initialization: O(V), where V is the number of vertices (courses).
• Topological Sort: O(V + E), since each node and edge is processed once.

Thus, the overall time complexity is O(V + E).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?