98% faster solution BFS with return array mimicing queue


  • 0
    A
    public class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            ArrayList[] nodes = new ArrayList[numCourses];
            int[] inDegree = new int[numCourses];
            int[] order = new int[numCourses];
            
            for(int i = 0; i < numCourses; i++) {
                nodes[i] = new ArrayList<Integer>();
            }
            
            for(int[] prereq : prerequisites) {
                int src = prereq[1];
                int dest = prereq[0];
                
                inDegree[dest]++;
                nodes[src].add(dest);
            }
            
            int pos = 0;
            
            for(int i = 0; i < numCourses; i++) {
                if(inDegree[i] == 0)
                    order[pos++] = i;
            }
            
            if(pos == 0) //There are no root candidates
                return new int[0];
            
            int currPos = 0;
            while(pos < numCourses) {
                int curr = order[currPos];
                int size = nodes[curr].size();
                
                for(int i = 0; i < size; i++) {
                    int child = (int)nodes[curr].get(i);
                    inDegree[child]--;
                    
                    if(inDegree[child] == 0)
                        order[pos++] = child;
                }
                
                currPos++;
                
                //We have successfully scheduled all courses when pos == len
                //In the worst case due to dependencies, currpos will have to run till len
                //Sometimes, when we have cycles, currpos will keep running and will soon exceed pos
                
                if(currPos > pos) { //When pos has not moved forward but currPos moves forward regardless
                    return new int[0];
                }
            }
            
            return order;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.