# (4 ms Java solution) Engineered Topological Sort

• 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>();
}
}

// 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;
}``````

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