# Course Schedule II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/course-schedule-ii)
Canonical: https://scaleengineer.com/dsa/problems/course-schedule-ii
**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), [Intuit](https://scaleengineer.com/companies/intuit), [Karat](https://scaleengineer.com/companies/karat), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Snowflake](https://scaleengineer.com/companies/snowflake), [VMware](https://scaleengineer.com/companies/vmware), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [eBay](https://scaleengineer.com/companies/ebay), [Netflix](https://scaleengineer.com/companies/netflix), [Salesforce](https://scaleengineer.com/companies/salesforce), [Tesla](https://scaleengineer.com/companies/tesla), [Citadel](https://scaleengineer.com/companies/citadel), [Snap](https://scaleengineer.com/companies/snap), [Zenefits](https://scaleengineer.com/companies/zenefits), [PhonePe](https://scaleengineer.com/companies/phonepe), [Databricks](https://scaleengineer.com/companies/databricks), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Anduril](https://scaleengineer.com/companies/anduril), [Workday](https://scaleengineer.com/companies/workday), [Remitly](https://scaleengineer.com/companies/remitly)
---
## 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 _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**.

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

**Constraints:**

* `1 <= numCourses <= 2000`
* `0 <= prerequisites.length <= numCourses * (numCourses - 1)`
* `prerequisites[i].length == 2`
* `0 <= ai, bi < numCourses`
* `ai != bi`
* All the pairs `[ai, bi]` are **distinct**.

# Approaches
## DFS with Adjacency Matrix
This approach uses Depth First Search with an adjacency matrix to detect cycles and find the topological ordering of courses.
**Time:** O(n^2) where n is the number of courses, due to the adjacency matrix representation · **Space:** O(n^2) for the adjacency matrix
**Pros:** Simple to understand and implement; Good for dense graphs; Easy to modify for additional requirements
**Cons:** Higher 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 to represent the course prerequisites. Then we perform DFS traversal while keeping track of visited nodes and nodes in the current path to detect cycles. If a cycle is detected, we return an empty array. Otherwise, we build the topological order during the DFS backtracking.

```java
class Solution {
    private boolean[][] adjMatrix;
    private boolean[] visited;
    private boolean[] path;
    private List<Integer> order;
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Initialize data structures
        adjMatrix = new boolean[numCourses][numCourses];
        visited = new boolean[numCourses];
        path = new boolean[numCourses];
        order = new ArrayList<>();
        
        // Build adjacency matrix
        for (int[] pre : prerequisites) {
            adjMatrix[pre[0]][pre[1]] = true;
        }
        
        // Check for cycles and build topological order
        for (int i = 0; i < numCourses; i++) {
            if (!visited[i] && hasCycle(i)) {
                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) {
        if (path[course]) return true;
        if (visited[course]) return false;
        
        path[course] = true;
        visited[course] = true;
        
        for (int i = 0; i < adjMatrix.length; i++) {
            if (adjMatrix[course][i] && hasCycle(i)) {
                return true;
            }
        }
        
        order.add(0, course);
        path[course] = false;
        return false;
    }
}
```
### Algorithm
1. Create an adjacency matrix to represent prerequisites
2. Initialize visited and path arrays for cycle detection
3. For each unvisited course:
   - Perform DFS traversal
   - Check for cycles
   - Add courses to result list during backtracking
4. Convert result list to array and return

## BFS with Adjacency List (Kahn's Algorithm)
This approach uses Breadth First Search with an adjacency list representation and keeps track of in-degrees of vertices to find a valid topological ordering.
**Time:** O(V + E) where V is the number of courses and E is the number of prerequisites · **Space:** O(V + E) for the adjacency list and queue
**Pros:** More efficient for sparse graphs; Better space complexity; Naturally finds topological order; Can detect cycles efficiently
**Cons:** Requires additional space for in-degree array; May not be as intuitive as DFS approach; Not as efficient for dense graphs
### Explanation
We use Kahn's algorithm which works by maintaining a queue of nodes with no prerequisites (in-degree = 0). We continuously process these nodes and reduce the in-degree of their dependent courses. When a course's in-degree becomes 0, it's added to the queue.

```java
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // Build adjacency list and calculate in-degrees
        List<List<Integer>> adj = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }
        
        // Add all courses with no prerequisites to queue
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }
        
        // Process courses in topological order
        int[] result = new int[numCourses];
        int index = 0;
        
        while (!queue.isEmpty()) {
            int course = queue.poll();
            result[index++] = course;
            
            for (int dependent : adj.get(course)) {
                inDegree[dependent]--;
                if (inDegree[dependent] == 0) {
                    queue.offer(dependent);
                }
            }
        }
        
        return index == numCourses ? result : new int[0];
    }
}
```
### Algorithm
1. Build adjacency list and calculate in-degrees
2. Initialize queue with courses having no prerequisites
3. While queue is not empty:
   - Remove a course
   - Add it to result
   - Reduce in-degree of dependent courses
   - Add new courses with in-degree 0 to queue
4. Return result if all courses are processed, empty array otherwise

# Solutions
### CSharp

```csharp
public class Solution {
    public int[] FindOrder(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 ans = new int[numCourses];
        var cnt = 0;
        while (q.Count > 0) {
            int i = q.Dequeue();
            ans[cnt++] = i;
            foreach(int j in g[i]) {
                if (--indeg[j] == 0) {
                    q.Enqueue(j);
                }
            }
        }
        return cnt == numCourses ? ans : new int[0];
    }
}
```

### Java

```java
class Solution {
public
  int[] findOrder(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[] ans = new int[numCourses];
    int cnt = 0;
    while (!q.isEmpty()) {
      int i = q.poll();
      ans[cnt++] = i;
      for (int j : g[i]) {
        if (--indeg[j] == 0) {
          q.offer(j);
        }
      }
    }
    return cnt == numCourses ? ans : new int[0];
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findOrder(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);
      }
    }
    vector<int> ans;
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      ans.push_back(i);
      for (int j : g[i]) {
        if (--indeg[j] == 0) {
          q.push(j);
        }
      }
    }
    return ans.size() == numCourses ? ans : vector<int>();
  }
};

```

### Python

```python
class Solution:
    # added from previous question while q : i = q . popleft () ans . append ( i ) # assumption is only one path # as in question 'You may assume that there are no duplicate edges in the input prerequisites.' for j in g [ i ]: indeg [ j ] -= 1 if indeg [ j ] == 0 : q . append ( j ) return ans if len ( ans ) == numCourses else []
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: g = defaultdict(list) indeg = [0] * numCourses for a, b in prerequisites: g[b]. append(a) indeg[a] += 1 q = deque([i for i, v in enumerate(indeg) if v == 0]) ans = []

```