Java beats 98% using DFS. Clean with detailed comments.


  • 0
    M

    One thing that makes this code fast is that I create a visited array to see if a node is unvisited, visited in the path, or visited in other paths before. This not only makes my code cleaner but also speed up my code, so I think its worth sharing. Hope this helps.

    public class Solution {
        int[] visited;
        //Mark a node into three states.
        //0 means unvisited, 1 means temporarily visited, 2 means visited.
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            visited=new int[numCourses];
            int[] topoArray=new int[numCourses];//Array to return later
            ArrayList<Integer> result=new ArrayList<Integer>();//Transfer this to array later
            ArrayList<Integer>[] adjList=new ArrayList[numCourses];
            
            for(int i=0;i<prerequisites.length;i++){
                if(adjList[prerequisites[i][0]]==null){//First time the number shows up will have to init
                    adjList[prerequisites[i][0]]=new ArrayList<Integer>();
                }
                adjList[prerequisites[i][0]].add(prerequisites[i][1]);
            }
            
            for(int i=0;i<numCourses;i++){
                if(visited[i]==0&&!dfs(adjList,result,i)) return new int[0];
                //If find cycle, dfs() will return false. So we can return [] here.
            }
            
            for(int i=0;i<numCourses;i++){
                topoArray[i]=result.get(i);//Transfer ArrayList to array. Might have better ways but this is an easy way.
            }
            
            return topoArray;
        }
        public boolean dfs(ArrayList<Integer>[] adjList,ArrayList<Integer> result,int point){
            if(visited[point]==2) return true;//2 means visited before in other path. So we can return here.
            if(visited[point]==1) return false;//1 means we've just visited in the path. This means we find a cycle.
            
            visited[point]=1;//Mark this node temporarily.
            ArrayList<Integer> tmp=adjList[point];
            if(tmp!=null){
                for(int i=0;i<tmp.size();i++){
                    if(!dfs(adjList,result,tmp.get(i))) return false;
                }
            }
            result.add(point);
            visited[point]=2;//Mark this node permanently.
            return true;
        }
    

Log in to reply
 

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