# Course Schedule
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/course-schedule)
Canonical: https://scaleengineer.com/dsa/problems/course-schedule
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Graph
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [DoorDash](https://scaleengineer.com/companies/doordash), [Flipkart](https://scaleengineer.com/companies/flipkart), [Intuit](https://scaleengineer.com/companies/intuit), [Karat](https://scaleengineer.com/companies/karat), [Nutanix](https://scaleengineer.com/companies/nutanix), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [Roblox](https://scaleengineer.com/companies/roblox), [Snowflake](https://scaleengineer.com/companies/snowflake), [VMware](https://scaleengineer.com/companies/vmware), [Visa](https://scaleengineer.com/companies/visa), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yelp](https://scaleengineer.com/companies/yelp), [eBay](https://scaleengineer.com/companies/ebay), [Coupang](https://scaleengineer.com/companies/coupang), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [Swiggy](https://scaleengineer.com/companies/swiggy), [Zenefits](https://scaleengineer.com/companies/zenefits), [LiveRamp](https://scaleengineer.com/companies/liveramp), [Anduril](https://scaleengineer.com/companies/anduril), [IXL](https://scaleengineer.com/companies/ixl), [CrowdStrike](https://scaleengineer.com/companies/crowdstrike), [Nordstrom](https://scaleengineer.com/companies/nordstrom), [Cruise](https://scaleengineer.com/companies/cruise), [Graviton](https://scaleengineer.com/companies/graviton)
---
## Problem
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`.

**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.

**Constraints:**

* `1 <= numCourses <= 2000`
* `0 <= prerequisites.length <= 5000`
* `prerequisites[i].length == 2`
* `0 <= ai, bi < numCourses`
* All the pairs prerequisites\[i\] are **unique**.

# Approaches
## DFS with Adjacency Matrix
This approach uses an adjacency matrix to represent the course prerequisites and performs DFS to detect cycles in the graph.
**Time:** O(n^2) where n is the number of courses, as we need to traverse the entire matrix · **Space:** O(n^2) for the adjacency matrix + O(n) for recursion stack
**Pros:** Simple to understand and implement; Good for dense graphs; Easy to modify for additional requirements
**Cons:** High space complexity due to adjacency matrix; Not efficient for sparse graphs; Unnecessary space usage when prerequisites are few
### Explanation
In this approach, we first create an adjacency matrix of size numCourses × numCourses to represent the prerequisites. For each prerequisite pair [a, b], we set matrix[a][b] = 1 indicating course b is required for course a. Then we perform DFS starting from each course to detect if there's a cycle in the graph.

```java
class Solution {
    private boolean dfs(int[][] matrix, boolean[] visited, boolean[] recursionStack, int course) {
        if (recursionStack[course]) return true; // cycle detected
        if (visited[course]) return false;
        
        visited[course] = true;
        recursionStack[course] = true;
        
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[course][i] == 1 && dfs(matrix, visited, recursionStack, i)) {
                return true;
            }
        }
        
        recursionStack[course] = false;
        return false;
    }
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[][] matrix = new int[numCourses][numCourses];
        for (int[] pre : prerequisites) {
            matrix[pre[0]][pre[1]] = 1;
        }
        
        boolean[] visited = new boolean[numCourses];
        boolean[] recursionStack = new boolean[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            if (dfs(matrix, visited, recursionStack, i)) {
                return false;
            }
        }
        return true;
    }
}```
### Algorithm
1. Create an adjacency matrix from prerequisites
2. For each course:
   - Perform DFS with visited and recursion stack arrays
   - If cycle is detected, return false
3. Return true if no cycles found

## DFS with Adjacency List
This approach uses an adjacency list representation and performs DFS to detect cycles in the graph, which is more space-efficient for sparse graphs.
**Time:** O(V + E) where V is number of courses and E is number of prerequisites · **Space:** O(V + E) for adjacency list + O(V) for recursion stack
**Pros:** More space-efficient for sparse graphs; Better time complexity for sparse graphs; Memory usage proportional to number of prerequisites
**Cons:** Slightly more complex implementation; Not as efficient for dense graphs; Recursive calls can lead to stack overflow for very large graphs
### Explanation
We create an adjacency list representation using a List<List<Integer>> where for each course, we store a list of its prerequisites. Then we perform DFS to detect cycles.

```java
class Solution {
    private boolean hasCycle(List<List<Integer>> adj, boolean[] visited, boolean[] recursionStack, int course) {
        if (recursionStack[course]) return true;
        if (visited[course]) return false;
        
        visited[course] = true;
        recursionStack[course] = true;
        
        for (int neighbor : adj.get(course)) {
            if (hasCycle(adj, visited, recursionStack, neighbor)) {
                return true;
            }
        }
        
        recursionStack[course] = false;
        return false;
    }
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        
        for (int[] pre : prerequisites) {
            adj.get(pre[0]).add(pre[1]);
        }
        
        boolean[] visited = new boolean[numCourses];
        boolean[] recursionStack = new boolean[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(adj, visited, recursionStack, i)) {
                return false;
            }
        }
        return true;
    }
}```
### Algorithm
1. Create an adjacency list from prerequisites
2. For each course:
   - Perform DFS with visited and recursion stack arrays
   - If cycle is detected, return false
3. Return true if no cycles found

## Kahn's Algorithm (Topological Sort)
This approach uses Kahn's algorithm for topological sorting, which is an iterative approach using indegree of vertices to detect cycles.
**Time:** O(V + E) where V is number of courses and E is number of prerequisites · **Space:** O(V + E) for adjacency list and queue
**Pros:** Non-recursive solution avoiding stack overflow; Efficient for both sparse and dense graphs; Can easily be modified to return the order of courses; More intuitive for course scheduling context
**Cons:** Requires additional space for queue and indegree array; May not be as intuitive for those unfamiliar with topological sort; Cannot provide cycle path if one exists
### Explanation
We use Kahn's algorithm which works by keeping track of courses with no prerequisites (indegree = 0) and removing them one by one, reducing the indegree of their dependent courses. If we can process all courses, there's no cycle.

```java
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegree = new int[numCourses];
        List<List<Integer>> adj = new ArrayList<>();
        
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        
        // Build adjacency list and calculate indegree
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
            indegree[pre[0]]++;
        }
        
        Queue<Integer> queue = new LinkedList<>();
        // Add all courses with no prerequisites to queue
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }
        
        int count = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;
            
            for (int neighbor : adj.get(course)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        return count == numCourses;
    }
}```
### Algorithm
1. Calculate indegree for each course
2. Add courses with indegree 0 to queue
3. While queue is not empty:
   - Remove a course and increment count
   - Reduce indegree of dependent courses
   - Add new courses with indegree 0 to queue
4. Return true if count equals total courses

# Solutions
### CSharp

```csharp
public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        var g = new List < int > [numCourses];
        for (int i = 0; i < numCourses; ++i) {
            g[i] = new List < int > ();
        }
        var indeg = new int[numCourses];
        foreach(var p in prerequisites) {
            int a = p[0], b = p[1];
            g[b].Add(a);
            ++indeg[a];
        }
        var q = new Queue < int > ();
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                q.Enqueue(i);
            }
        }
        var cnt = 0;
        while (q.Count > 0) {
            int i = q.Dequeue();
            ++cnt;
            foreach(int j in g[i]) {
                if (--indeg[j] == 0) {
                    q.Enqueue(j);
                }
            }
        }
        return cnt == numCourses;
    }
}
```

### Java

```java
public class Course_Schedule { public class Solution_bfs { public boolean canFinish ( int numCourses , int [][] prerequisites ) { // Kahn's Algorithm if ( numCourses <= 0 ) { return false ; } if ( prerequisites == null || prerequisites . length == 0 ) { return true ; } int [] inDegree = new int [ numCourses ]; // 1. setup indgree count for ( int [] edge : prerequisites ) { inDegree [ edge [ 0 ]]++; } Queue < Integer > queue = new LinkedList <>(); // 2. start from node with no indgree, i.e. no prerquisites for this course for ( int i = 0 ; i < inDegree . length ; i ++) { if ( inDegree [ i ] == 0 ) { queue . offer ( i ); } } List < Integer > result = new ArrayList <>(); while (! queue . isEmpty ()) { int currentCourse = queue . poll (); result . add ( currentCourse ); for ( int [] edge : prerequisites ) { if ( edge [ 1 ] == currentCourse ) { // if a course requires current course if (-- inDegree [ edge [ 0 ]] == 0 ) // -1, since current course is taken, and fulfill course edge[0] queue . offer ( edge [ 0 ]); } } } return result . size () == numCourses ; } } public class Solution_dfs { public boolean canFinish ( int numCourses , int [][] prerequisites ) { if ( prerequisites == null || prerequisites . length < 2 ) { return true ; } // 0 for not visited，1 for globally visited，-1 for visisted AND on current path int [] isVisited = new int [ numCourses ]; List < List < Integer >> graph = new ArrayList <>(); // 1. build graph for ( int i = 0 ; i < numCourses ; i ++) { graph . add ( new ArrayList <>()); } for ( int [] each: prerequisites ) { graph . get ( each [ 1 ]). add ( each [ 0 ]); } // 2. dfs for ( int i = 0 ; i < numCourses ; i ++) { if (! dfs ( i , isVisited , graph )) { return false ; } } return true ; } private boolean dfs ( int courseIndex , int [] isVisited , List < List < Integer >> graph ) { if ( isVisited [ courseIndex ] == 1 ) { return true ; } if ( isVisited [ courseIndex ] == - 1 ) { return false ; // cycle found } isVisited [ courseIndex ] = - 1 ; for ( Integer next: graph . get ( courseIndex )) { if (! dfs ( next , isVisited , graph )) { return false ; } } isVisited [ courseIndex ] = 1 ; return true ; } } } ////// class Solution { public boolean canFinish ( int numCourses , int [][] prerequisites ) { List < Integer >[] g = new List [ numCourses ]; Arrays . setAll ( g , k -> new ArrayList <>()); int [] indeg = new int [ numCourses ]; for ( var p : prerequisites ) { int a = p [ 0 ], b = p [ 1 ]; g [ b ]. add ( a ); ++ indeg [ a ]; } Deque < Integer > q = new ArrayDeque <>(); for ( int i = 0 ; i < numCourses ; ++ i ) { if ( indeg [ i ] == 0 ) { q . offer ( i ); } } int cnt = 0 ; while (! q . isEmpty ()) { int i = q . poll (); ++ cnt ; for ( int j : g [ i ]) { if (-- indeg [ j ] == 0 ) { q . offer ( j ); } } } return cnt == numCourses ; } }
```

### CPP

```cpp
class Solution {
public:
  bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
    vector<vector<int>> g(numCourses);
    vector<int> indeg(numCourses);
    for (auto &p : prerequisites) {
      int a = p[0], b = p[1];
      g[b].push_back(a);
      ++indeg[a];
    }
    queue<int> q;
    for (int i = 0; i < numCourses; ++i) {
      if (indeg[i] == 0) {
        q.push(i);
      }
    }
    int cnt = 0;
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      ++cnt;
      for (int j : g[i]) {
        if (--indeg[j] == 0) {
          q.push(j);
        }
      }
    }
    return cnt == numCourses;
  }
};

```

### Python

```python
''' >>> from collections import defaultdict >>> a = defaultdict(int) >>> a defaultdict(<type 'int'>, {}) >>> >>> a['hehehe'] 0 >>> a defaultdict(<type 'int'>, {'hehehe': 0}) >>> a = defaultdict(list) >>> a defaultdict(<type 'list'>, {}) >>> a['hehehe'] [] >>> a defaultdict(<type 'list'>, {'hehehe': []}) ''' class Solution : def canFinish ( self , numCourses : int , prerequisites : List [ List [ int ]]) -> bool : g = defaultdict ( list ) indeg = [ 0 ] * numCourses for a , b in prerequisites : g [ b ]. append ( a ) indeg [ a ] += 1 cnt = 0 q = deque ([ i for i , v in enumerate ( indeg ) if v == 0 ]) while q : i = q . popleft () cnt += 1 for j in g [ i ]: indeg [ j ] -= 1 if indeg [ j ] == 0 : q . append ( j ) return cnt == numCourses
```