(4 ms Java solution) Engineered Topological Sort


  • 1
    A

    Explanation: Use the same Tarjan's algorithm for Topological Sort as other solutions. Some engineering tricks include:

    • Build the "incoming" adjacency list instead of the normal one, and output the results directly without reversing the array.

    • Use directly an int[] array of length numCourses+1, with the first item is the number of added courses so far

    • Use the int[] array to store temporary / permanently visited nodes (visited = 1 ==> temporary visited, 2 ==> permanently visited).

    • Check stop condition early before going the recursive call

    I ran the code many times. The average running time is 5 ms, two times it took 4ms.

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int n = prerequisites.length;
    
        // build the incoming adjacency list
        ArrayList<Integer>[] pos = new ArrayList[numCourses];
        for (int i = 0; i < n; i++) {
            int j = prerequisites[i][0];
            if (pos[j] == null) {
                pos[j] = new ArrayList<Integer>();
            }
            pos[j].add(prerequisites[i][1]);
        }
    
        // mark nodes as unvisited (0), temporary visited (1) or permanently visited (2)
        int[] visited = new int[numCourses];
    
        int[] order = new int[numCourses+1];
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 1) return new int[0];
            else if (visited[i] == 2) continue;
            else if (!canFinish(pos, order, visited, i)) {
                return new int[0];
            }
        }
        return Arrays.copyOfRange(order, 1, order[0]+1);
    }
    
    private boolean canFinish(ArrayList<Integer>[] pos, int[] order,
                              int[] visited, int start) {
        if (pos[start] != null) {
            visited[start] = 1;
            for (int i = 0; i < pos[start].size(); i++) {
                int dest = pos[start].get(i).intValue();
    
                // check before the recursive call
                if (visited[dest] == 1) return false;
                else if (visited[dest] == 2) continue;
                if (!canFinish(pos, order, visited, dest)) return false;
            }
            pos[start] = null;
        }
    
        // update the results incrementally
        order[++order[0]] = start;
        visited[start] = 2;
        return true;
    }

Log in to reply
 

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