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]
graph[s].add(d)
return topo_sort(graph)
```

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

Seconded, thanks for explaining this so fully.

OO solution

```
class Node:
def __init__(self, val):
self.val = val
self.children = set()
self.parents = set()
def add_child(self, node):
self.children.add(node)
def add_parent(self, node):
self.parents.add(node)
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.add_child(node)
node.add_parent(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
visited.add((prev_val, val))
val_to_children[prev_val].add(val)
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`

?