Course Schedule II


Problem Statement :


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.


Solution :



title-img 


                            Solution in C :

int cmpfunc(const void* a, const void* b){
    int* arr1 = *(int**)a;
    int* arr2 = *(int**)b;
    
    return arr1[1] - arr2[1];
}

int BTS(int** arr, int arrSize, int val){
    int left = 0, right = arrSize-1;
    int mid;
    while(left < right){
        mid = left + (right - left)/2 ;
        if(arr[mid][1] >= val)
            right = mid;
        else
            left = mid + 1;
    }
    if(arr[left][1] == val)
        return left;
    else
        return -1;
}

int* findOrder(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize, int* returnSize){
    int* prereqCn = calloc(numCourses , sizeof(int));
    for(int i = 0; i < prerequisitesSize; i++){
        prereqCn[ prerequisites[i][0] ]++;
    }
    //depend test case : queue can be smaller 
    int* queue = malloc(1000 * sizeof(int));
    int Qidx  = 0;
    for(int i = 0; i < numCourses; i++){
        if(prereqCn[i] == 0){
            queue[Qidx] = i;
            Qidx++;
        }
    }
    if(prerequisitesSize > 0)
        qsort(prerequisites, prerequisitesSize, sizeof(int*), cmpfunc);
    int* ans = malloc( numCourses * sizeof(int)) ;
    int andIdx = 0;
    while(Qidx){
        Qidx--;
        int val = queue[Qidx];
        ans[andIdx] = val;
        andIdx++;
        if(prerequisitesSize > 0){
            int k = BTS(prerequisites, prerequisitesSize, val);
            if(k != -1){
                while(k < prerequisitesSize && prerequisites[k][1] == val){
                    prereqCn[ prerequisites[k][0] ]--;
                    if( prereqCn[ prerequisites[k][0] ] == 0  ){
                        queue[Qidx] = prerequisites[k][0] ;
                        Qidx++;  
                    }
                    k++;
                }
            }
        }
    }
    //if collision happen, then no ans
    if(andIdx != numCourses){
        *returnSize = 0;
        free(ans);
        return NULL;
    }
    else
        *returnSize = numCourses;
    return ans;
}
                        


                        Solution in C++ :

typedef vector<vector<int>> vvi;
typedef vector<int> vi;
class Solution {
private:
    void dfs(int s, vvi& graph, vi& pro, vi& res, bool& cycle) {
        if (pro[s] > 0) {
            if (pro[s] == 1) cycle = true;
            return;
        }
        pro[s] = 1;
        for (int u: graph[s]) dfs(u, graph, pro, res, cycle);
        pro[s] = 2;
        res.push_back(s);
    }

public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vvi graph(numCourses);
        vi pro(numCourses);
        vi res, buf;
        bool cycle = false;

        for (int i = 0; i < prerequisites.size(); i++) {
            int a = prerequisites[i][0], b = prerequisites[i][1];
            graph[b].push_back(a);
        }

        for (int i = 0; i < numCourses; i++) {
            dfs(i, graph, pro, res, cycle);
            if (cycle == true) return buf;
        }

        reverse(res.begin(), res.end());
        return res;
    }
};
                    


                        Solution in Java :

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
       int[] indegree = new int[numCourses];
       boolean[] visited = new boolean[prerequisites.length];
       boolean[] done = new boolean[numCourses];
       int[] res = new int[numCourses];

       for (int[] p : prerequisites) {
           indegree[p[1]]++;
       }
       int index = 0;
        boolean hasNewVertex = true;
        while(hasNewVertex) {
            hasNewVertex = false;
            for (int i = 0; i < prerequisites.length; i++) {
                if (!visited[i]) {
                    int cur = prerequisites[i][0];
                    int pre = prerequisites[i][1];
                    if (indegree[cur] == 0) { 
                        // start from indegree == 0, cut edges, until no indegree = 0
                        visited[i] = true;
                        indegree[pre]--;
                        hasNewVertex = true;
                        if(!done[cur]){
                            done[cur] = true;
                            res[index++] = cur;
                        }
                    }
                }
            }
        }

        for (int i = 0 ; i < numCourses; i++) {
            if (!done[i]) {
                res[index++] = i;
            }
        }
        
        for (int i = 0; i < numCourses/2; i++) {
            int temp = res[i];
            res[i] = res[numCourses-1-i];
            res[numCourses-1-i] = temp;
        }

        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] != 0) {
                return new int[]{};
            }
        }

        return res;
    }
}
                    


                        Solution in Python : 
                            
class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = {}
        
        for i in range(numCourses):
            graph[i]=[]
        
        for c,pc in prerequisites:
            graph[c].append(pc)
            
        ans = []
        finallyVisited=set()
        visited = set()
        def dfs(course):
            if course in visited:
                return False
            
            if course in finallyVisited:
                return True
            
            visited.add(course)

            for nei in graph[course]:
                if not dfs(nei):
                    return False
            
            ans.append(course)
            finallyVisited.add(course)
            visited.remove(course)
            return True


        for key,val in graph.items():
            if not dfs(key):
                return []

        return ans


View More Similar Problems

Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →

Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →

Binary Search Tree : Insertion

You are given a pointer to the root of a binary search tree and values to be inserted into the tree. Insert the values into their appropriate position in the binary search tree and return the root of the updated binary tree. You just have to complete the function. Input Format You are given a function, Node * insert (Node * root ,int data) { } Constraints No. of nodes in the tree <

View Solution →

Tree: Huffman Decoding

Huffman coding assigns variable length codewords to fixed length input characters based on their frequencies. More frequent characters are assigned shorter codewords and less frequent characters are assigned longer codewords. All edges along the path to a character contain a code digit. If they are on the left side of the tree, they will be a 0 (zero). If on the right, they'll be a 1 (one). Only t

View Solution →

Binary Search Tree : Lowest Common Ancestor

You are given pointer to the root of the binary search tree and two values v1 and v2. You need to return the lowest common ancestor (LCA) of v1 and v2 in the binary search tree. In the diagram above, the lowest common ancestor of the nodes 4 and 6 is the node 3. Node 3 is the lowest node which has nodes and as descendants. Function Description Complete the function lca in the editor b

View Solution →

Swap Nodes [Algo]

A binary tree is a tree which is characterized by one of the following properties: It can be empty (null). It contains a root node only. It contains a root node with a left subtree, a right subtree, or both. These subtrees are also binary trees. In-order traversal is performed as Traverse the left subtree. Visit root. Traverse the right subtree. For this in-order traversal, start from

View Solution →