Problem #210: Course Schedule II

Intuition & Strategy Breakdown

Use Kahn's Algorithm (BFS topological sort) tracking in-degrees. Append processed nodes to ordering array; if output length == numCourses return order.

Python Solution

from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        adj = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for dest, src in prerequisites:
            adj[src].append(dest)
            indegree[dest] += 1
        
        queue = deque([i for i in range(numCourses) if indegree[i] == 0])
        res = []
        
        while queue:
            u = queue.popleft()
            res.append(u)
            for v in adj[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    queue.append(v)
                    
        return res if len(res) == numCourses else []

Java Solution

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List[] adj = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) adj[i] = new ArrayList<>();
        int[] indegree = new int[numCourses];
        
        for (int[] p : prerequisites) {
            adj[p[1]].add(p[0]);
            indegree[p[0]]++;
        }
        
        Queue queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }
        
        int[] res = new int[numCourses];
        int count = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            res[count++] = u;
            for (int v : adj[u]) {
                if (--indegree[v] == 0) queue.offer(v);
            }
        }
        
        return count == numCourses ? res : new int[0];
    }
}