Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Mohammed Dh Abbas
the proper solution

Mohammed Dh Abbas

Jun 8, 2024

The official solution is bad and disagree with how it was done. how uses queue.remove() ???. that's O(operation)

This is a the proper solution to the question

from collections import deque class Solution: def __init__(self): self.orders = [] # this is a backtracking / permutatinal + topological solution def topo(self, path, seen): # base case if len(path) == len(self.graph): self.orders.append(path[:]) return # instead of using queue to procee the next 0 node we recurse and loop to find the 0 node for node in self.graph: if self.indegree[node] == 0 and not seen.get(node): seen[node] = True path.append(node) for nex_node in self.graph[node]: self.indegree[nex_node] -= 1 self.topo(path, seen) # undo the change as the values gets used when one path completes for nex_node in self.graph[node]: self.indegree[nex_node] += 1 seen[node] = False path.pop() def printOrders(self, tasks, prerequisites): # edge cases if tasks == 0: return self.orders elif tasks == 1: self.orders.append([0]) return self.orders # build graph and indegree self.graph = {} self.indegree = {} for i in range(tasks): self.graph[i] = [] self.indegree[i] = 0 for before, after in prerequisites: self.graph[before].append(after) self.indegree[after] += 1 self.topo([], {}) return self.orders

0

0

Comments
Comments

On this page