educative.io

Educative

No need for hashMap, space complexity can be O(v)

We can use the same logic, but we use int[] array to store indegree.

// time: O(V + E)
// space: O(V)

for example
while (!queue.isEmpty()) {
int pre = queue.poll();
for (int[] pair : prerequisites) {
if (pre == pair[1]) {
indegree[pair[0]]–;
if (indegree[pair[0]] == 0) {
queue.offer(pair[0]);
}
}
}
}