Just to remark that you don’t need to waste space in the sortedOrder array.
from collections import deque, defaultdict
def can_construct(originalSeq, sequences):
incoming = defaultdict(int)
outgoing = defaultdict(list)
elements = set()
for seq in sequences:
for i in range(len(seq) - 1):
parent = seq[i]
child = seq[i + 1]
elements.add(parent)
elements.add(child)
incoming[child] += 1
outgoing[parent].append(child)
sources = deque()
for e in elements:
if incoming[e] == 0:
sources.append(e)
next_in_original = 0
while sources:
v = sources.popleft()
if sources or next_in_original >= len(originalSeq) or v != originalSeq[next_in_original]:
return False
next_in_original += 1
for e in outgoing[v]:
incoming[e] -= 1
if incoming[e] == 0:
sources.append(e)
return next_in_original == len(originalSeq)
Type your question above this line.
Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/6460939912085504