# Kahn's Algorithm (Java)

• My favorite way to perform topological sorts is Kahn's algorithm. You just have to make sure you keep track of the # of totalEdges + incomingEdges w/ O(1) access time to keep it fast.

``````class Solution {

public int[] findOrder(int numCourses, int[][] preqs) {

// If remaining edges then return empty

int totalEdges = 0;

int[] incomingEdges = new int[numCourses];

HashMap<Integer, ArrayList<Integer>> edges = new HashMap<Integer, ArrayList<Integer>>();

for(int i=0;i<numCourses;i++){

edges.put(i, new ArrayList<Integer>());

}

for(int[] req: preqs){

incomingEdges[req[0]]++;

totalEdges++;

}

ArrayList<Integer> order = new ArrayList<Integer>();

for(int i=0;i<numCourses;i++) if(incomingEdges[i] == 0) edgeless.add(i);

while(edgeless.size() > 0){

int n = edgeless.remove();

ArrayList<Integer> neighbors = edges.get(n);

for(int neighbor: neighbors){

incomingEdges[neighbor]--;

totalEdges--;

}

}

if(totalEdges > 0) return new int[0];

int[] tr = new int[order.size()];

for(int i=0;i<order.size();i++) tr[i] = order.get(i);

return tr;

}

}``````

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