The Sequence Reconstruction problem requires determining whether a given original sequence, denoted as org, can be uniquely reconstructed from a list of sequences, seqs. Each sequence in seqs is a subsequence of the original, and elements in these sequences are ordered as in org. The reconstruction is considered successful if:
seqs and it matches org.org must be used, and no elements are reused or omitted.seqs describes a (possibly partial) ordering between elements.
The main challenge is to check if the information in seqs is sufficient and unambiguous to reconstruct org without any alternative possibilities.
At first glance, one might think of generating all possible sequences that satisfy the ordering constraints from seqs and checking if only one matches org. However, this brute-force approach is computationally expensive and impractical for large inputs.
Instead, we can view the problem as one of topological sorting in a directed graph. Each number in org is a node, and the orderings from seqs form directed edges. If there is exactly one way to perform the topological sort and that sort equals org, reconstruction is possible and unique.
The key insight is to use Breadth-First Search (BFS) for topological sorting, and at each step, ensure there is only one node with zero indegree (i.e., only one possible next element). If at any point multiple nodes are available, multiple valid sequences exist, violating uniqueness.
The solution can be broken down into the following steps:
seqs.org are present in seqs. If not, reconstruction is impossible.org exactly, with no extra or missing elements.We use hash maps (dictionaries) for adjacency lists and indegree counts for efficient O(1) access and updates.
Example:
org = [1,2,3]
seqs = [[1,2], [1,3], [2,3]]
Adjacency: 1 → {2,3}, 2 → {3}, 3 → {}
Indegree: 1:0, 2:1, 3:2
org.
Thus, the answer is true: the sequence can be uniquely reconstructed.
Brute-force approach: Generating all possible sequences consistent with seqs is exponential in the number of elements (O(n!)), which is infeasible for large inputs.
Optimized approach (topological sort):
seqs. We visit each node and edge once.
This efficiency is possible because we use hash maps for quick lookups and process each edge and node only once.
The Sequence Reconstruction problem is elegantly solved by interpreting it as a topological sorting challenge. By constructing a directed graph from the ordering constraints in seqs and performing a BFS-based topological sort, we can efficiently determine if the original sequence org can be uniquely reconstructed. The crucial insight is to ensure at each step that only one node is available for selection, guaranteeing uniqueness. This approach is both efficient and robust, leveraging fundamental graph algorithms to solve a seemingly complex sequencing problem.
from collections import defaultdict, deque
class Solution:
def sequenceReconstruction(self, org, seqs):
if not org or not seqs:
return False
# Build graph and indegree
graph = defaultdict(set)
indegree = defaultdict(int)
nodes = set()
for seq in seqs:
for num in seq:
nodes.add(num)
for seq in seqs:
for i in range(1, len(seq)):
prev, curr = seq[i-1], seq[i]
if curr not in graph[prev]:
graph[prev].add(curr)
indegree[curr] += 1
# All org elements must be present
if nodes != set(org):
return False
# Initialize queue with zero indegree nodes
queue = deque([x for x in org if indegree[x] == 0])
idx = 0
while queue:
if len(queue) > 1:
return False # Multiple ways to reconstruct
node = queue.popleft()
if org[idx] != node:
return False
idx += 1
for nei in graph[node]:
indegree[nei] -= 1
if indegree[nei] == 0:
queue.append(nei)
return idx == len(org)
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
using namespace std;
class Solution {
public:
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
if (org.empty() || seqs.empty()) return false;
unordered_map<int, unordered_set<int>> graph;
unordered_map<int, int> indegree;
unordered_set<int> nodes;
for (const auto& seq : seqs)
for (int num : seq)
nodes.insert(num);
for (const auto& seq : seqs) {
for (int i = 1; i < seq.size(); ++i) {
int prev = seq[i-1], curr = seq[i];
if (!graph[prev].count(curr)) {
graph[prev].insert(curr);
indegree[curr]++;
}
}
}
if (nodes.size() != org.size())
return false;
for (int num : org)
if (!nodes.count(num))
return false;
queue<int> q;
for (int num : org)
if (indegree[num] == 0)
q.push(num);
int idx = 0;
while (!q.empty()) {
if (q.size() > 1) return false;
int node = q.front(); q.pop();
if (org[idx++] != node) return false;
for (int nei : graph[node]) {
indegree[nei]--;
if (indegree[nei] == 0)
q.push(nei);
}
}
return idx == org.size();
}
};
import java.util.*;
class Solution {
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
if (org == null || org.length == 0 || seqs == null || seqs.size() == 0)
return false;
Map<Integer, Set<Integer>> graph = new HashMap<>();
Map<Integer, Integer> indegree = new HashMap<>();
Set<Integer> nodes = new HashSet<>();
for (List<Integer> seq : seqs)
for (int num : seq)
nodes.add(num);
for (List<Integer> seq : seqs) {
for (int i = 1; i < seq.size(); i++) {
int prev = seq.get(i-1), curr = seq.get(i);
if (!graph.containsKey(prev)) graph.put(prev, new HashSet<>());
if (!graph.get(prev).contains(curr)) {
graph.get(prev).add(curr);
indegree.put(curr, indegree.getOrDefault(curr, 0) + 1);
}
}
}
if (nodes.size() != org.length) return false;
for (int num : org)
if (!nodes.contains(num))
return false;
Queue<Integer> queue = new LinkedList<>();
for (int num : org)
if (!indegree.containsKey(num))
queue.offer(num);
int idx = 0;
while (!queue.isEmpty()) {
if (queue.size() > 1) return false;
int node = queue.poll();
if (org[idx++] != node) return false;
if (graph.containsKey(node)) {
for (int nei : graph.get(node)) {
indegree.put(nei, indegree.get(nei) - 1);
if (indegree.get(nei) == 0)
queue.offer(nei);
}
}
}
return idx == org.length;
}
}
var sequenceReconstruction = function(org, seqs) {
if (!org.length || !seqs.length) return false;
const graph = {};
const indegree = {};
const nodes = new Set();
for (const seq of seqs)
for (const num of seq)
nodes.add(num);
for (const seq of seqs) {
for (let i = 1; i < seq.length; i++) {
const prev = seq[i-1], curr = seq[i];
if (!graph[prev]) graph[prev] = new Set();
if (!graph[prev].has(curr)) {
graph[prev].add(curr);
indegree[curr] = (indegree[curr] || 0) + 1;
}
}
}
if (nodes.size !== org.length) return false;
for (const num of org)
if (!nodes.has(num)) return false;
const queue = [];
for (const num of org)
if (!indegree[num]) queue.push(num);
let idx = 0;
while (queue.length) {
if (queue.length > 1) return false;
const node = queue.shift();
if (org[idx++] !== node) return false;
if (graph[node]) {
for (const nei of graph[node]) {
indegree[nei] -= 1;
if (indegree[nei] === 0)
queue.push(nei);
}
}
}
return idx === org.length;
};