> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/201-300/course-schedule-ii.md).

# 210. Course Schedule II

### Description

There are a total of `n` courses you have to take labelled from `0` to `n - 1`.

Some courses may have `prerequisites`, for example, if `prerequisites[i] = [ai, bi]` this means you must take the course `bi` before the course `ai`.

Given the total number of courses `numCourses` and a list of the `prerequisite` pairs, 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**.

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

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/course-schedule-ii/)
* [ProgramCreek](https://www.programcreek.com/2014/06/leetcode-course-schedule-ii-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="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].
{% endtab %}

{% tab title="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].
{% endtab %}

{% tab title="Example 3" %}
**Input:** numCourses = 1, prerequisites = \[]

**Output:** \[0]
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        
        int[] result = new int[numCourses];
        
        if(prerequisites.length == 0) {
            for(int i = 0; i < numCourses; i++) {
                result[i] = i;
            }
            return result;
        }
        
        int[] prereqCounter = new int[numCourses];
        for(int i = 0; i < prerequisites.length; i++) {
            prereqCounter[prerequisites[i][0]]++;
        }
        
        LinkedList<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < numCourses; i++) {
            if(prereqCounter[i] == 0) queue.add(i);
        }
        
        int noPrereqCourses = queue.size();
        int j = 0;
        
        while(!queue.isEmpty()) {
            int course = queue.remove();
            result[j++] = course;
            
            for(int i = 0; i < prerequisites.length; i++) {
                if(prerequisites[i][1] == course) {
                    prereqCounter[prerequisites[i][0]]--;
                    if(prereqCounter[prerequisites[i][0]] == 0) {
                        queue.add(prerequisites[i][0]);
                        noPrereqCourses++;
                    }
                }
            }
        }
        
        if(noPrereqCourses == numCourses) {
            return result;
        }
        
        return new int[0];
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private int index = 0;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        
        int[] result = new int[numCourses];
        
        if(prerequisites.length == 0) {
            for(int i = 0; i < numCourses; i++) {
                result[i] = i;
            }
            return result;
        }
        
        ArrayList[] courses = new ArrayList[numCourses];
        for(int i = 0; i < numCourses; i++) {
            courses[i] = new ArrayList<Integer>();
        }
        
        for(int[] pre: prerequisites) {
            courses[pre[0]].add(pre[1]);
        }
        
        int[] processedStatus = new int[numCourses];
        
        for(int i = 0; i < numCourses; i++) {
            if(processedStatus[i] == 0) {
                if(isCycleExist(i, courses, processedStatus, result)) {
                    return new int[0];
                }
            }
        }
        
        return result;
    }
    
        private boolean isCycleExist(int u,
                                 ArrayList[] courses, 
                                 int[] processedStatus,
                                 int[] orderedCourses) {
        if(processedStatus[u] == 2) return true;
                
        processedStatus[u] = 2;
        
        ArrayList<Integer> course = courses[u];
        for(int v = 0; v < course.size(); v++) {
            if(processedStatus[course.get(v)] != 1) {
                if(isCycleExist((int)course.get(v), courses, processedStatus, orderedCourses)) {
                    return true;
                }
            }
        }
        
        processedStatus[u] = 1;
        orderedCourses[index++] = u;
        
        return false;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*