Simple BFS with Explanation (7 ms, beat 93%)


  • 1
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List[] graph = new ArrayList[numCourses];
        int[] degree = new int[numCourses]; 
        Queue queue = new LinkedList(); 
        
        // return an array in the end
        int[] ret = new int[numCourses]; 
        
        for (int i = 0; i < numCourses; i++){
            graph[i] = new ArrayList(); 
        }
        
        // populate graph (a list of arrayList)
        for (int i = 0; i < prerequisites.length; i++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]); 
            degree[prerequisites[i][0]]++; 
        }
        
        int count = 0; 
    
        // start point 
        for(int i = 0; i < numCourses; i++){
            if (degree[i] == 0){
                queue.add(i);
                ret[count] = i; 
                count++; 
            }
        }
        
        // BFS search 
        while (!queue.isEmpty()){
            int cur = (int)queue.poll(); 
            for (int i = 0; i < graph[cur].size(); i++){
                int next = (int) graph[cur].get(i);
                degree[next]--;
                if (degree[next] == 0){
                    queue.add(next);
                    ret[count] = next; 
                    count++; 
                }
            }
        }
        
        // return the order, if possible
        return count == numCourses? ret: new int[0]; 
    }

Log in to reply
 

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