Course Schedule II

210.Course Schedule II

Graph

Breadth-First Search

Topological Sort

Problem Statement:

There are n courses you have to take, labeled from 0 to n-1. Some courses have prerequisites. Return the ordering of courses you should take to finish all courses. If impossible, return empty array.

Example:

Input:

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

→

Output:

[0,1,2,3]

Algorithm:

1. Build adjacency list representation
2. Calculate in-degree for each node
3. Start with nodes having 0 in-degree
4. Process neighbors and update in-degrees

Complexity:

Time: O(V + E) | Space: O(V + E) where V is vertices, E is edges

Java Solution:

public int[] findOrder(int numCourses, int[][] prerequisites) {
    // Result array and pointer
    int[] res = new int[numCourses];
    int k = 0;
    
    // Keep track of in-degrees
    int[] inDegree = new int[numCourses];
    
    // Build adjacency list
    Map<Integer, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < numCourses; i++) 
        map.put(i, new ArrayList<>());
    
    // Process prerequisites and count in-degrees
    for (int[] pair : prerequisites) {
        map.get(pair[1]).add(pair[0]);
        inDegree[pair[0]]++;
    }
    
    // Add all nodes with 0 in-degree to queue
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) 
        if (inDegree[i] == 0) 
            q.offer(i);
    
    // Process queue
    while (!q.isEmpty()) {
        int curr = q.poll();
        res[k++] = curr;  // Add to result
        // Process neighbors
        for (int course : map.get(curr)) {
            inDegree[course]--;
            if (inDegree[course] == 0) 
                q.add(course);
        }
    }
    
    // Return result if valid ordering exists
    return k == numCourses ? res : new int[0];
}

Python Solution:

def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    # Initialize graph and in-degree array
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    result = []
    
    # Build graph and count in-degrees
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        in_degree[course] += 1
    
    # Add all 0 in-degree nodes to queue
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    
    # Process queue
    while queue:
        curr = queue.popleft()
        result.append(curr)
        for neighbor in graph[curr]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                
    return result if len(result) == numCourses else []

C++ Solution:

vector<int> findOrder(int numCourses, vectorint>>& prerequisites) {
    // Initialize graph and in-degree array
    vectorint>> graph(numCourses);
    vector<int> inDegree(numCourses, 0);
    vector<int> result;
    
    // Build graph and count in-degrees
    for (const auto& pre : prerequisites) {
        graph[pre[1]].push_back(pre[0]);
        inDegree[pre[0]]++;
    }
    
    // Add all 0 in-degree nodes to queue
    queue<int> q;
    for (int i = 0; i < numCourses; i++)
        if (inDegree[i] == 0)
            q.push(i);
    
    // Process queue
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        result.push_back(curr);
        
        for (int next : graph[curr]) {
            inDegree[next]--;
            if (inDegree[next] == 0)
                q.push(next);
        }
    }
    
    // Return result if valid ordering exists
    return result.size() == numCourses ? result : vector<int>();
}