Course Schedule II

Problem Description

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

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.

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]

Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    # Create adjacency list
    graph = [[] for _ in range(numCourses)]
    for course, prereq in prerequisites:
        graph[course].append(prereq)
    
    # 0 = unvisited, 1 = visiting, 2 = visited
    visited = [0] * numCourses
    order = []
    
    def hasCycle(course: int) -> bool:
        if visited[course] == 1:  # Found cycle
            return True
        if visited[course] == 2:  # Already visited
            return False
        
        visited[course] = 1  # Mark as visiting
        
        # Check all prerequisites
        for prereq in graph[course]:
            if hasCycle(prereq):
                return True
        
        visited[course] = 2  # Mark as visited
        order.append(course)
        return False
    
    # Check each course
    for course in range(numCourses):
        if hasCycle(course):
            return []
    
    return order[::-1]  # Reverse for correct order

Kahn's Algorithm Solution:


def findOrder(numCourses: int, prerequisites: List[List[int]]) -> List[int]:
    # Create adjacency list and indegree count
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1
    
    # Add all courses with no prerequisites to queue
    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    order = []
    
    while queue:
        course = queue.popleft()
        order.append(course)
        
        # Reduce indegree for all dependent courses
        for next_course in graph[course]:
            indegree[next_course] -= 1
            if indegree[next_course] == 0:
                queue.append(next_course)
    
    return order if len(order) == numCourses else []

Java Solution


class Solution {
    private List order = new ArrayList<>();
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Create adjacency list
        List> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int[] prereq : prerequisites) {
            graph.get(prereq[0]).add(prereq[1]);
        }
        
        // 0 = unvisited, 1 = visiting, 2 = visited
        int[] visited = new int[numCourses];
        
        // Check each course
        for (int course = 0; course < numCourses; course++) {
            if (hasCycle(course, graph, visited)) {
                return new int[0];
            }
        }
        
        // Convert List to array
        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            result[i] = order.get(i);
        }
        return result;
    }
    
    private boolean hasCycle(int course, List> graph, int[] visited) {
        if (visited[course] == 1) return true;   // Found cycle
        if (visited[course] == 2) return false;  // Already visited
        
        visited[course] = 1;  // Mark as visiting
        
        // Check all prerequisites
        for (int prereq : graph.get(course)) {
            if (hasCycle(prereq, graph, visited)) {
                return true;
            }
        }
        
        visited[course] = 2;  // Mark as visited
        order.add(course);
        return false;
    }
}

C++ Solution


class Solution {
private:
    vector order;
    
    bool hasCycle(int course, vector>& graph, vector& visited) {
        if (visited[course] == 1) return true;   // Found cycle
        if (visited[course] == 2) return false;  // Already visited
        
        visited[course] = 1;  // Mark as visiting
        
        // Check all prerequisites
        for (int prereq : graph[course]) {
            if (hasCycle(prereq, graph, visited)) {
                return true;
            }
        }
        
        visited[course] = 2;  // Mark as visited
        order.push_back(course);
        return false;
    }
    
public:
    vector findOrder(int numCourses, vector>& prerequisites) {
        // Create adjacency list
        vector> graph(numCourses);
        for (const auto& prereq : prerequisites) {
            graph[prereq[0]].push_back(prereq[1]);
        }
        
        // 0 = unvisited, 1 = visiting, 2 = visited
        vector visited(numCourses, 0);
        
        // Check each course
        for (int course = 0; course < numCourses; course++) {
            if (hasCycle(course, graph, visited)) {
                return vector();
            }
        }
        
        return order;
    }
};

JavaScript Solution


/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function(numCourses, prerequisites) {
    // Create adjacency list
    const graph = Array.from({ length: numCourses }, () => []);
    for (const [course, prereq] of prerequisites) {
        graph[course].push(prereq);
    }
    
    const visited = new Array(numCourses).fill(0);
    const order = [];
    
    const hasCycle = (course) => {
        if (visited[course] === 1) return true;   // Found cycle
        if (visited[course] === 2) return false;  // Already visited
        
        visited[course] = 1;  // Mark as visiting
        
        // Check all prerequisites
        for (const prereq of graph[course]) {
            if (hasCycle(prereq)) {
                return true;
            }
        }
        
        visited[course] = 2;  // Mark as visited
        order.push(course);
        return false;
    };
    
    // Check each course
    for (let course = 0; course < numCourses; course++) {
        if (hasCycle(course)) {
            return [];
        }
    }
    
    return order.reverse();
};

C# Solution


public class Solution {
    private List order = new List();
    
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        // Create adjacency list
        List> graph = new List>();
        for (int i = 0; i < numCourses; i++) {
            graph.Add(new List());
        }
        
        foreach (var prereq in prerequisites) {
            graph[prereq[0]].Add(prereq[1]);
        }
        
        // 0 = unvisited, 1 = visiting, 2 = visited
        int[] visited = new int[numCourses];
        
        // Check each course
        for (int course = 0; course < numCourses; course++) {
            if (HasCycle(course, graph, visited)) {
                return new int[0];
            }
        }
        
        return order.ToArray();
    }
    
    private bool HasCycle(int course, List> graph, int[] visited) {
        if (visited[course] == 1) return true;   // Found cycle
        if (visited[course] == 2) return false;  // Already visited
        
        visited[course] = 1;  // Mark as visiting
        
        // Check all prerequisites
        foreach (int prereq in graph[course]) {
            if (HasCycle(prereq, graph, visited)) {
                return true;
            }
        }
        
        visited[course] = 2;  // Mark as visited
        order.Add(course);
        return false;
    }
}

Complexity Analysis

Time Complexity: O(V + E) where V is the number of courses and E is the number of prerequisites
Space Complexity: O(V + E) for the adjacency list and visited array

Solution Explanation

There are two main approaches to solve this problem:

DFS with Cycle Detection:
- Build adjacency list
- Use visited array to track states
- Detect cycles using DFS
- Build order during backtracking
Kahn's Algorithm:
- Build adjacency list and indegree count
- Start with courses having no prerequisites
- Remove dependencies as courses are completed
- Build order during process

Key Points

Graph representation
Cycle detection
Order building
Dependency resolution

Common Pitfalls

Incorrect graph building
Missing cycle detection
Wrong order building
Edge cases

Edge Cases

No prerequisites
Single course
Cyclic dependencies
Disconnected components