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?