Q18 Course Schedule - LeetCode 207 (kahn's algorithm)

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        /* Q18 of graph playlist , we will do this through kahn's  algo or topological sort
        assume the problem to be a graph where ever node has a dependency/prequisite to 
        another node also known as indegree.
        */

        //taking input 
        int n = numCourses;
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        //initializing arraylist
        for(int i = 0 ; i < n ; i++)
        graph.add(new ArrayList<>());

        //making graph
        for(int pre[] : prerequisites)
        graph.get(pre[1]).add(pre[0]); 
        
        //calling kahn's  algo 
        ArrayList<Integer> ans = kahn(n , graph);

        //if all vertix are covered in kahn's algo return true , else false
        if(ans.size() == n )
        return true;

        return false;

    }

    public ArrayList<Integer> kahn(int n , ArrayList<ArrayList<Integer>> graph){
        ArrayList<Integer> ans = new ArrayList<>(); //can also count instead arraylist

        //finding indegree
        int[] indegree = new int[n];

        for(int i = 0 ;i < n ; i++){
            for(int nbr : graph.get(i))
            indegree[nbr] ++;
        }

        //making a q and adding all nodes with indegree 0
        LinkedList<Integer> q = new LinkedList<>();

        for(int i = 0 ; i < n ;i++){
            if(indegree[i] == 0)
            q.addLast(i);
        }

        //now running kahn's algo
        while(q.size()>0){
            int rem = q.removeFirst();
            ans.add(rem);                   //storing in topological order

            //decreasing indegree/dependency of neighours
            for(int nbr : graph.get(rem)){
                indegree[nbr] --;

                //if node's indegree becomes 0 we add it to the q
                if(indegree[nbr] == 0)
                q.addLast(nbr);
            }
        }

        return ans;
    }
}