# Reconstructing Sequence - Graph / Directed Graph / Topological Sort

Test#5
seq [5 3] is not a subsequence of the original [3 1 4 2]

if you run your solution youâ€™ll find out.

Where is Test#5 seq [5 3]?

Actually repeated edges is not a problem at all and we could use list instead of set to store neighbours. For example if A points to B two times, then counts[B] would be 2 and we substract 1 twice as B would be neighbour of A twice too.

Why do we need to sort both arrays in the equality check function? Donâ€™t both arrays need to have nodes positioned in the same index to be considered equal?

that would not happen as you decrement the â€śdependencyâ€ť counter by one when A is removed. Since you remove A only once, you would decrease the counter once as wellâ€¦

-Problem description does not specify anywhere that â€śThe orginal sequence is a permutation of the integers from 1 to nâ€ť. \

• Regardless, to create the graph we traverse all sequences in seqs so the time complexity is O(n*m) as each of m seq can be n elements longâ€¦

Python solution does not sort any arrays

from typing import List
from collections import deque

def sequence_reconstruction(original: List[int], seqs: List[List[int]]) â†’ bool:
# WRITE YOUR BRILLIANT CODE HERE

``````# 1- Create graph from seqs and in this case the graph will
#    contain a set of two conteguise integer in each seq of seqs,
#    Then call sequence_reconstruction with graph as input
#
# 2- Create the kahn's algo:
#    a- Create count_parent counting the number of parents for
#       each node in seqs.
#    b- Create topo_sorting. However, in this case the uniquence is
#       determined by the number of nodes in the queue.
#       If more than one node is in the queue at given itteration/processing
#       of the sorting that mean that for each node kahn algo can generate an
#       original. Hence we need to make sure only one node at the time in the queue.
#

def count_parent(graph):
# Hash Map for counting the parent for each node of the graph
counts = {node: 0 for node in graph}
for parent in graph:
for node in graph[parent]:
counts[node] += 1

return counts

def topo_sort(graph):
result = []
q = deque()

counts = count_parent(graph)
for node in counts:
if counts[node] == 0:
q.append(node)

while(len(q) > 0):
if len(q) > 1:
return False

node = q.popleft()
result.append(node)
for child in graph[node]:
counts[child] -= 1
if counts[child] == 0:
q.append(child)

return result == original

# build graph using a set
n = len(original)
graph = {node: set() for node in range(1, n+1)}

for subseq in seqs:
for i in range(len(subseq) - 1):
s,d = subseq[i], subseq[i+1]

``````

In Java solution, as edges are stored with Set, no need to check again before insertion, I mean the following check on line 22:

if (!graph.get(earlyNum).contains(lateNum)) {

Looks like Test#6 is invalid: we cannot create subsequence {1, 1, 3} from original: {1 3 2 5 4} only â€śby deleting elements from `s`â€ť.

Going further, if the presence of duplicates is not forbidden, then the provided solution does not work correctly for the following scenario: seq {3, 2, 3, 1}; subseqs: {3, 2, 3}, {2, 3, 1} => return false.
While this test case complies with the problem statement, the idea of topo sort wonâ€™t work due to the simultaneous presence of 3->2 and 2->3 edges.

If the stated above is correct, could you please update the problem description + test#6 (or provide another solution that would cover the current conditions)?

1 Like

Moreover, test#6 passes as a side-effect of

``````original.equals(reconstructed);
``````

Under the hood, the method returns false as the queue is empty at the beginning of the while loop (as inDegree for `1` was not 0 due to duplication, so no starting nodes were added).

1 Like

Seconded, thanks for explaining this so fully.

1 Like

OO solution

``````class Node:
def __init__(self, val):
self.val = val
self.children = set()
self.parents = set()

def sequence_reconstruction(original: List[int], seqs: List[List[int]]) -> bool:
val_to_node = {}
for seq in seqs:
prev_node = None
for val in seq:
if val not in val_to_node:
node = Node(val)
val_to_node[val] = node
else:
node = val_to_node[val]
if prev_node:
prev_node = node
for val in original:
if val not in val_to_node:
val_to_node[val] = Node(val)
queue = deque([node for node in val_to_node.values() if not node.parents])

rst = []
while queue:
if len(queue) > 1:
return False
node = queue.popleft()
rst.append(node.val)
for child in node.children:
child.parents.remove(node)
if not child.parents:
queue.append(child)

return original == rst
``````

Kahnâ€™s solution

``````def sequence_reconstruction(original: List[int], seqs: List[List[int]]) -> bool:
val_to_children = defaultdict(set)
indegree = defaultdict(int)
visited = set()
for seq in seqs:
for prev_val, val in zip(seq[:-1], seq[1:]):
if (prev_val, val) in visited:
continue
indegree[val] += 1

queue = deque([val for val in original if indegree[val] == 0])
rst = []
while queue:
if len(queue) > 1:
return False
val = queue.popleft()
rst.append(val)
for child in val_to_children[val]:
indegree[child] -= 1
if indegree[child] == 0:
queue.append(child)
return original == rst
``````

Why is `original` even needed in this problem?
I didnâ€™t use it in my solution, but still passed all the test.

Also, wonâ€™t the `equals` function always return `true`?