Standard 6ms DFS Java solution beats 93% with comments


  • 0
    J

    Nothing fancy here, just a standard DFS approach to the problem. I also put some comments in the code to make it more readable.

     public class Solution {
            //implementing my own version of IntHolder to store results
            class IntHolder{
                public int value;
                public IntHolder(int a){
                    this.value = a;
                }
            }
            public int[] findOrder(int numCourses, int[][] prerequisites) {
                ArrayList<Integer>[] graph = new ArrayList[numCourses];
                int[] visited = new int[numCourses];
                int[] results = new int[numCourses];
                //construct the graph structure
                for (int i = 0; i < prerequisites.length; i++){
                    if(prerequisites[i].length == 2){
                    	if (graph[prerequisites[i][0]] == null)
                    		graph[prerequisites[i][0]] = new ArrayList<Integer>();
                        graph[prerequisites[i][0]].add(prerequisites[i][1]);
                    }
                }
                IntHolder order = new IntHolder(0);
                //do dfs on the graph
                for (int i = 0; i < numCourses; i++){
                    if(!!!doDfs(graph, visited, i, order, results)){
                        results = new int[0]; 
                        return results;
                    }
                }
                return results;
            }
            
            //doDfs will return false if cycle is detected
            private boolean doDfs(ArrayList<Integer>[] graph, int[] visited,
                                   int visitingCourse, IntHolder order, int[] results){
            	if (visited[visitingCourse] == 0){ //do DFS only when not visited before
                    visited[visitingCourse] = -1;      //visiting course assign a -1 value
                    if (graph[visitingCourse] != null){
                        for (Integer d: graph[visitingCourse]){
                            if(!!!doDfs(graph, visited, d, order, results)) 
                                return false;
                        }
                    }
                    visited[visitingCourse] = ++order.value;   //visited course assign an order value
                    results[order.value-1] = visitingCourse;   //record the visiting course its correct order in the result
            	} else {
            		if (visited[visitingCourse] == -1)  //cycle detected if hitting a visiting course again.
            			return false;
            	}
            	return true;
            }
        }

Log in to reply
 

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