# 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)?

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).