Course Schedule II

Brute Force — Repeated Scanning for Available Courses — Watch how we repeatedly scan all courses to find one whose prerequisites are satisfied, picking available courses one at a time.

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // Build prerequisite sets for each course
        vector<unordered_set<int>> prereqs(numCourses);
        for (auto& p : prerequisites) {
            prereqs[p[0]].insert(p[1]);
        }
        
        vector<int> result;
        vector<bool> completed(numCourses, false);
        
        for (int round = 0; round < numCourses; round++) {
            bool found = false;
            for (int course = 0; course < numCourses; course++) {
                if (completed[course]) continue;
                
                // Check if all prerequisites are completed
                bool canTake = true;
                for (int pre : prereqs[course]) {
                    if (!completed[pre]) {
                        canTake = false;
                        break;
                    }
                }
                
                if (canTake) {
                    result.push_back(course);
                    completed[course] = true;
                    found = true;
                    break;
                }
            }
            if (!found) return {}; // Cycle detected
        }
        
        return result;
    }
};

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        # Build prerequisite sets for each course
        prereqs = [set() for _ in range(numCourses)]
        for a, b in prerequisites:
            prereqs[a].add(b)
        
        result = []
        completed = set()
        
        for _ in range(numCourses):
            found = False
            for course in range(numCourses):
                if course in completed:
                    continue
                
                # Check if all prerequisites are completed
                if prereqs[course].issubset(completed):
                    result.append(course)
                    completed.add(course)
                    found = True
                    break
            
            if not found:
                return []  # Cycle detected
        
        return result

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Build prerequisite sets for each course
        Set<Integer>[] prereqs = new HashSet[numCourses];
        for (int i = 0; i < numCourses; i++) {
            prereqs[i] = new HashSet<>();
        }
        for (int[] p : prerequisites) {
            prereqs[p[0]].add(p[1]);
        }
        
        int[] result = new int[numCourses];
        boolean[] completed = new boolean[numCourses];
        int idx = 0;
        
        for (int round = 0; round < numCourses; round++) {
            boolean found = false;
            for (int course = 0; course < numCourses; course++) {
                if (completed[course]) continue;
                
                boolean canTake = true;
                for (int pre : prereqs[course]) {
                    if (!completed[pre]) {
                        canTake = false;
                        break;
                    }
                }
                
                if (canTake) {
                    result[idx++] = course;
                    completed[course] = true;
                    found = true;
                    break;
                }
            }
            if (!found) return new int[0]; // Cycle detected
        }
        
        return result;
    }
}

DFS-Based Topological Sort — Three-Color Traversal — Watch how DFS explores the dependency graph using white/gray/black coloring, and builds the topological order by pushing finished nodes onto a stack.

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for (auto& p : prerequisites) {
            graph[p[1]].push_back(p[0]);
        }
        
        // 0 = white, 1 = gray, 2 = black
        vector<int> color(numCourses, 0);
        vector<int> order;
        bool hasCycle = false;
        
        function<void(int)> dfs = [&](int node) {
            if (hasCycle) return;
            color[node] = 1; // gray
            for (int neighbor : graph[node]) {
                if (color[neighbor] == 1) {
                    hasCycle = true;
                    return;
                }
                if (color[neighbor] == 0) {
                    dfs(neighbor);
                }
            }
            color[node] = 2; // black
            order.push_back(node);
        };
        
        for (int i = 0; i < numCourses; i++) {
            if (color[i] == 0) {
                dfs(i);
                if (hasCycle) return {};
            }
        }
        
        reverse(order.begin(), order.end());
        return order;
    }
};

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[b].append(a)
        
        # 0 = white, 1 = gray, 2 = black
        color = [0] * numCourses
        order = []
        has_cycle = False
        
        def dfs(node: int) -> None:
            nonlocal has_cycle
            if has_cycle:
                return
            color[node] = 1  # gray
            for neighbor in graph[node]:
                if color[neighbor] == 1:
                    has_cycle = True
                    return
                if color[neighbor] == 0:
                    dfs(neighbor)
            color[node] = 2  # black
            order.append(node)
        
        for i in range(numCourses):
            if color[i] == 0:
                dfs(i)
                if has_cycle:
                    return []
        
        return order[::-1]

class Solution {
    private List<List<Integer>> graph;
    private int[] color;
    private List<Integer> order;
    private boolean hasCycle;
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
        }
        
        color = new int[numCourses]; // 0=white, 1=gray, 2=black
        order = new ArrayList<>();
        hasCycle = false;
        
        for (int i = 0; i < numCourses; i++) {
            if (color[i] == 0) {
                dfs(i);
                if (hasCycle) return new int[0];
            }
        }
        
        Collections.reverse(order);
        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            result[i] = order.get(i);
        }
        return result;
    }
    
    private void dfs(int node) {
        if (hasCycle) return;
        color[node] = 1;
        for (int neighbor : graph.get(node)) {
            if (color[neighbor] == 1) {
                hasCycle = true;
                return;
            }
            if (color[neighbor] == 0) {
                dfs(neighbor);
            }
        }
        color[node] = 2;
        order.add(node);
    }
}

Kahn's Algorithm — BFS Layer-by-Layer Topological Sort — Watch how Kahn's algorithm processes courses in BFS order, decrementing in-degrees and enqueueing courses as their prerequisites are fulfilled.

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> inDegree(numCourses, 0);
        
        for (auto& p : prerequisites) {
            graph[p[1]].push_back(p[0]);
            inDegree[p[0]]++;
        }
        
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        vector<int> result;
        while (!q.empty()) {
            int course = q.front();
            q.pop();
            result.push_back(course);
            
            for (int dependent : graph[course]) {
                inDegree[dependent]--;
                if (inDegree[dependent] == 0) {
                    q.push(dependent);
                }
            }
        }
        
        return result.size() == numCourses ? result : vector<int>();
    }
};

from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        graph = [[] for _ in range(numCourses)]
        in_degree = [0] * numCourses
        
        for a, b in prerequisites:
            graph[b].append(a)
            in_degree[a] += 1
        
        queue = deque()
        for i in range(numCourses):
            if in_degree[i] == 0:
                queue.append(i)
        
        result = []
        while queue:
            course = queue.popleft()
            result.append(course)
            
            for dependent in graph[course]:
                in_degree[dependent] -= 1
                if in_degree[dependent] == 0:
                    queue.append(dependent)
        
        return result if len(result) == numCourses else []

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
            inDegree[p[0]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int[] result = new int[numCourses];
        int idx = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            result[idx++] = course;
            
            for (int dependent : graph.get(course)) {
                inDegree[dependent]--;
                if (inDegree[dependent] == 0) {
                    queue.offer(dependent);
                }
            }
        }
        
        return idx == numCourses ? result : new int[0];
    }
}