207. Course Schedule

Medium

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.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Examples

Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    # 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
    
    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
        return False
    
    # Check each course
    for course in range(numCourses):
        if hasCycle(course):
            return False
    
    return True

Topological Sort Solution:


def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    # 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])
    count = 0
    
    while queue:
        course = queue.popleft()
        count += 1
        
        # 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 count == numCourses

Java Solution


class Solution {
    public boolean canFinish(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 false;
            }
        }
        
        return true;
    }
    
    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
        return false;
    }
}

C++ Solution


class Solution {
public:
    bool canFinish(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 false;
            }
        }
        
        return true;
    }
    
private:
    bool hasCycle(int course, const 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
        return false;
    }
};

JavaScript Solution


/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    // Create adjacency list
    const graph = Array.from({ length: numCourses }, () => []);
    for (const [course, prereq] of prerequisites) {
        graph[course].push(prereq);
    }
    
    // 0 = unvisited, 1 = visiting, 2 = visited
    const visited = new Array(numCourses).fill(0);
    
    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
        return false;
    };
    
    // Check each course
    for (let course = 0; course < numCourses; course++) {
        if (hasCycle(course)) {
            return false;
        }
    }
    
    return true;
};

C# Solution


public class Solution {
    public bool CanFinish(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 false;
            }
        }
        
        return true;
    }
    
    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
        return false;
    }
}

Complexity Analysis

Solution Explanation

There are two main approaches to solve this problem:

Key Points

Common Pitfalls

Edge Cases