# Python: Detailed & easy to understand solution

• Solution with discussion https://discuss.leetcode.com/topic/72895/python-detailed-easy-to-understand-solution

Sequence Reconstruction https://leetcode.com/problems/sequence-reconstruction/

Verify Unique Topological Sort Order

**What does a super sequence really mean? **

• It means a topological sort of input graph. Therefore every sequence (within the sequences) will be a subsequences of org. How will you check this condition? Every edge (u,v) in sequence will honor this precedence in org i.e. index_position(u) < index_position(v)
• For a sequence [5,2,3,6], it is enough to test the edges [5,2], [2,3], and [3,6]. This automatically implies [5,3] and [2,6].

**What is meant by the super sequence being unique? **

• In other words, when will the topological sort be unique? If and only if every consecutive items in org are edges then we have a unique sequence. Use an example: [1,2] and [1,3] will give us two valid super-sequences: [1,2,3] or [1,3,2]. There is no unique sequence since there is no precendence defined for nodes 2 and 3. Here is a wikipedia article about this: https://en.wikipedia.org/wiki/Topological_sorting#Uniqueness

Key Examples to Consider

• Empty sequence is an error
[1]
[]

• Any sequence item not in org is an Error
[5,3,2,4,1]
[[5,3,2,4],[4,1],[1],[3],[2,4],[1,1000000000]]

[5,3,2,4,1]
[[5,3,2,4],[4,1],[1],[3],[2,4], [1000000000]]

• Self direction or a cycle is an error. Hence: pos[seq[i]] >= pos[seq[i+1]]
[1]
[[1,1]]

• Make sure all orig items are marked
[1]
[[],[]]

Code

``````class Solution(object):
def sequenceReconstruction(self, org, seqs):
"""
:type org: List[int]
:type seqs: List[List[int]]
:rtype: bool
"""
if not seqs:
return False
pos, marked, orig_marked = {x:idx for idx,x in enumerate(org)}, set([]), set([])
for seq in seqs:
for i in range(len(seq)):
if seq[i] in pos: