# 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]);
}
}
}
}

Can you describe more?

You are missing the graph formation. IMO.

Cheers

I agree with you @Gaurav7, it needs the graph formation so it ends with the same space complexity. I used the same approach so here is the full code, in case anybody is interested:

``````from collections import deque

def topological_sort(vertices, edges):
incoming = [0 for _ in range(vertices)]
outgoing = [[] for _ in range(vertices)]
for p, c in edges:
incoming[c] += 1
outgoing[p] += [c]

sources = deque()
for i in range(vertices):
if incoming[i] == 0:
sources.append(i)

order = []
while sources:
v = sources.popleft()
order.append(v)
for e in outgoing[v]:
incoming[e] -= 1
if incoming[e] == 0:
sources.append(e)

if len(order) != vertices:
return []
return order``````