Problem Explanation

We need to find if the given sequence org can be uniquely reconstructed from the sequence in seqs. Here, org is a sequence which is permutation of integers from 1 to n. The reconstruction means that we have to build a shortest common supersequence of the sequence in seqs. In other words, we need to build shortest sequence which includes all sequences in seqs as their sub-sequences. The condition here is that, there must be only unique sequence that can be reconstructed from seqs, and it has to be org sequence.

Let's take a simple example,

org sequence: [1,2,3]

seqs: [[1,2],[1,3]]

In the example above, [1,2,3] is not the only sequence that can be reconstructed because [1,3,2] is also a valid sequence that can be reconstructed. So the output will be false.

Approach

The function takes org and seqs as its arguments. The function works by first building a directed graph(in form of adjacency list) from the given seqs. The nodes of this graph are the elements from the org sequence. There exists a directed edge between any two elements if they appear in the sequences in the same order. For example, if [1,2] is a sequence, there exists a directed edge from 1 to 2.

During this process, the function also maintains the in-degrees of all nodes (i.e., count of incoming edges for every node).

Then, the function performs topological sorting on this graph by starting from the nodes with 0 in-degree. During this process, if at anytime, there is more than one node with 0 in-degree, it means that there are multiple possible paths and hence, there are multiple different ways to reconstruct the sequence, so we end up returning false.

If there is only one node with 0 in-degree at all times, it means that there is only one unique path. In this case, the topologically sorted sequence should match the given org sequence. So, we check this condition and based on that return true or false.

Python Solution

1
2python
3from collections import defaultdict, deque
4
5class Solution:
6    def sequenceReconstruction(self, org: List[int], seqs: List[List[int]]) -> bool:
7        # Step 1: Initialize the graph
8        indegree, graph = defaultdict(int), defaultdict(set)
9        for seq in seqs:
10            for num in seq:
11                indegree[num] = 0
12
13        # Step 2: Build the graph
14        for seq in seqs:
15            if len(seq) == 1: continue
16            for i in range(1, len(seq)):
17                if seq[i] not in graph[seq[i - 1]]:
18                    graph[seq[i - 1]].add(seq[i])
19                    indegree[seq[i]] += 1
20
21        # Step 3: Find all sources
22        sources = deque([k for (k, v) in indegree.items() if v == 0])
23        org_index = 0
24
25        # Step 4: BFS
26        while sources:
27            if len(sources) != 1:
28                return False
29            if org[org_index] != sources[0]:
30                return False
31            vertex = sources.popleft()
32            org_index += 1
33            for child in graph[vertex]:
34                indegree[child] -= 1
35                if indegree[child] == 0:
36                    sources.append(child)
37        return org_index == len(org) and org_index == len(indegree)

Java Solution

1
2java
3class Solution {
4    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
5        Map<Integer, List<Integer>> map = new HashMap<>();
6        Map<Integer, Integer> indegree = new HashMap<>();
7        for (List<Integer> seq : seqs) {
8            for (int i = 0; i < seq.size(); i++) {
9                map.putIfAbsent(seq.get(i), new ArrayList<>());
10                indegree.putIfAbsent(seq.get(i), 0);
11                if (i > 0) {
12                    map.get(seq.get(i - 1)).add(seq.get(i));
13                    indegree.put(seq.get(i), indegree.get(seq.get(i)) + 1);
14                }
15            }
16        }
17
18        Queue<Integer> q = new LinkedList<>();
19        for (int key : indegree.keySet()) {
20            if (indegree.get(key) == 0) q.offer(key);
21        }
22
23        int index = 0;
24        while (!q.isEmpty()) {
25            int size = q.size();
26            if (size > 1) return false;
27            int curr = q.poll();
28            if (index == org.length || curr != org[index++]) return false;
29            for (int next : map.get(curr)) {
30                indegree.put(next, indegree.get(next) - 1);
31                if (indegree.get(next) == 0) q.offer(next);
32            }
33        }
34        return index == org.length && index == map.size();
35    }
36}

C# Solution

1
2CSharp
3public class Solution {
4    public bool SequenceReconstruction(int[] org, IList<IList<int>> seqs) {
5        Dictionary<int, HashSet<int>> graph = new Dictionary<int, HashSet<int>>();
6        Dictionary<int, int> degree = new Dictionary<int, int>();
7
8        foreach (var seq in seqs) {
9            for (int i = 0; i < seq.Count; i++) {
10                if (!graph.ContainsKey(seq[i])) {
11                    graph[seq[i]] = new HashSet<int>();
12                    degree[seq[i]] = 0;
13                }
14                if (i > 0 && graph[seq[i - 1]].Add(seq[i])) {
15                    degree[seq[i]] += 1;
16                }
17            }
18        }
19
20        if (degree.Count != org.Length) return false;
21
22        Queue<int> queue = new Queue<int>(degree.Where(kvp => kvp.Value == 0).Select(kvp => kvp.Key));
23
24        int index = 0;
25
26        while (queue.Count == 1) {
27            int current = queue.Dequeue();
28
29            if (org[index++] != current) return false;
30
31            foreach (int neighbor in graph[current]) {
32                degree[neighbor] -= 1;
33                if (degree[neighbor] == 0) queue.Enqueue(neighbor);
34            }
35        }
36
37        return index == org.Length;
38    }
39}

JavaScript Solution

1
2JavaScript
3var sequenceReconstruction = function(org, seqs) {
4    let graph = new Map(), degree = new Map(), zeroDegree = [], map = new Map(); 
5    let idx = 0;
6    for(let i = 0; i < seqs.length; i++){
7        for(let j = 0; j < seqs[i].length; j++){
8            if(!graph.has(seqs[i][j])) graph.set(seqs[i][j], []);
9            if(!degree.has(seqs[i][j])) degree.set(seqs[i][j], 0);
10            map.set(seqs[i][j], true);
11            if(j > 0 && !graph.get(seqs[i][j-1]).includes(seqs[i][j])) {
12                graph.get(seqs[i][j-1]).push(seqs[i][j]);
13                degree.set(seqs[i][j], degree.get(seqs[i][j]) + 1);
14            }
15        }
16    }
17    if(map.size != org.length) return false;
18    for(let [key, val] of degree.entries()){
19        if(val == 0) zeroDegree.push(key);
20    }
21    while(zeroDegree.length == 1){
22        let cur = zeroDegree.pop();
23        if(org[idx++] != cur) return false;
24        for(let next of graph.get(cur)){
25            degree.set(next, degree.get(next) - 1);
26            if(degree.get(next) == 0) zeroDegree.push(next);
27        }
28    }
29    return idx == org.length;
30};

In each of the above solutions, the graphs are generated by linking the numbers in seqs based on their order. The degrees of each node (total number of edges directed towards it) are also calculated. Queue data structure is used to store and manipulate nodes with zero-degree. Topological sorting is performed by continuously removing the only number with zero-degree left in a deque and matching it with the org sequence. If at any point, there are no such numbers or there are two such numbers, it is not possible to reconstruct the sequence uniquely and hence, the solutions return false.

In situations where topological sorting continues until all elements of org are visited and all numbers have been checked to have a degree equal to zero once, the program returns true, thus indicating that the sequence org can be uniquely constructed from sequences seqs. This step of topological sorting ensures that the sequence follows the order and uniqueness constraint, hence making the solution correct and efficient.

Space complexity of all these solutions is O(n) due to the usage of dictionaries or HashSets to record degrees and build graphs. The time complexity is also O(n) where 'n' is the total number of integers present in all the given sequences combined. This is because each integer is processed only once. Thus, the algorithm can be considered highly efficient when dealing with large inputs as well.

In conclusion, whether you're working with Python, Java, JavaScript or C#, the methodology remains the same for determining whether a sequence can be uniquely reconstructed from a list of sequences. This consistent method together with an efficient algorithm makes for an optimal solution to the problem.