Course Schedule II – LeetCode

You have to attend n number of courses (from 0 to n-1) where some of the courses have prerequisites. For instance: pair [2, 1] represents to attend course 2 you must have taken course 1. Given an integer n representing the total number of courses and the list of courses with their prerequisites. We need to return any order in which you can complete all the n courses. If there is no possible answer return an empty array. If there are multiple answers return which one you want.

Example

Input :  4

[ [1,0], [2,0], [3,1], [3,2] ]

Output : [0, 1, 2, 3,]

Input : 2

[ [1, 0] ]

Output : [0, 1,]

Using Breadth First Search

Algorithm for Course Schedule II – LeetCode

1. Initialize an integer n representing the number of courses and a 2D array course for storing courses and their prerequisites.
2. If the course array is a null print empty array.
3. Create an array pCounter of size n to store the courses which need prerequisites.
4. Move from 0 to n-1 and increment pCounter[course[i][0]].
5. Create a vector queue to store all the prerequisites.
6. Move from 0 to n-1 and check if the value in pCounter for the current index is 0, add the current index in the queue.
7. Initialize an array result of size n.
8. While the queue is not empty remove the last element in the queue and store it in the result array and an integer c.
9. Create an inner loop and check if the value at [][1] in course array is equal to c decrement pCounter[course[i][0]].
10. Check if pCounter[course[i][0]] is 0 add course[i][0] in queue.
11. Print the result array.

Implementation

C++ Program for Course Schedule II – LeetCode

#include <bits/stdc++.h> 
using namespace std; 
  
int len = 4;

void findOrder(int n, int course[4][2]){
    if(course == NULL){
        cout<<"empty array";
    }
    
    int pCounter[n];
    for(int i=0; i<len; i++){
        pCounter[course[i][0]]++;
    }
    
    vector<int> queue;
    for(int i=0; i<n; i++){
        if(pCounter[i]==0){
            queue.push_back(i);
        }
    }
    
    int numNoPre = queue.size();
    
    int result[n];
    int j=0;
    
    while(queue.size()!=0){
        int c = 0;
        if(!queue.empty()){
            c = queue.back();
            queue.pop_back();
        }    
        result[j++]=c;
        
        for(int i=0; i<len; i++){
            if(course[i][1]==c){
                pCounter[course[i][0]]--;
                if(pCounter[course[i][0]]==0){
                    queue.push_back(course[i][0]);
                    numNoPre++;
                }
            }
        
        }
    }
    
    cout<<"[";
    for(int i=0; i<n; i++){
        cout<<result[i]<<",";
    }
    cout<<"]";
}
  
int main(){
    
    int n = 4;
        int course[4][2] = {{1,0}, {2,0}, {3,1}, {3,2}};
        
        findOrder(n, course);
    
    return 0; 
}

[0,2,1,3,]

Java Program for Course Schedule II – LeetCode

import java.util.*;
    
class selection{
    static int[] findOrder(int n, int[][] course) {
        if(course == null){
            throw new IllegalArgumentException("empty array");
        }
        
        int len = course.length;
        
        if(len == 0){
            int[] res = new int[n];
            for(int m=0; m<n; m++){
                res[m]=m;
            }
            return res;
        }
    
        int[] pCounter = new int[n];
        for(int i=0; i<len; i++){
            pCounter[course[i][0]]++;
        }
        
        LinkedList<Integer> queue = new LinkedList<Integer>();
        for(int i=0; i<n; i++){
            if(pCounter[i]==0){
                queue.add(i);
            }
        }
        
        int numNoPre = queue.size();
        
        int[] result = new int[n];
        int j=0;
        
        while(!queue.isEmpty()){
            int c = queue.remove();
            result[j++]=c;
            
            for(int i=0; i<len; i++){
                if(course[i][1]==c){
                    pCounter[course[i][0]]--;
                    if(pCounter[course[i][0]]==0){
                        queue.add(course[i][0]);
                        numNoPre++;
                    }
                }
            
            }
        }
        
        if(numNoPre==n){
            return result;
        }
        else{
            return new int[0];
        }
    }
    
    public static void main (String[] args) {
        int n = 4;
        int[][] course = {{1,0}, {2,0}, {3,1}, {3,2}};
        
        int[] result = findOrder(n, course);
        
        System.out.print("[");
        for(int i=0; i<result.length; i++){
            System.out.print(result[i]+",");
        }
        System.out.print("]");
    }
}

[0,1,2,3,]

Complexity Analysis for Course Schedule II – LeetCode

Time Complexity

O(Q*M) where Q is the size of vector or list containing prerequisites and M is the number of rows i.e. number of given pairs.

Space Complexity

O(M*N) where M denotes the number of rows and N denotes the number of columns in the given course array.

References