Sequence Reconstruction

medium topological sort graph

Problem

Given a target permutation and a list of subsequences, return whether the target is the unique sequence whose every consecutive pair appears in some subsequence.

Inputnums = [1,2,3], seqs = [[1,2],[1,3],[2,3]]

Outputtrue

Edges 1→2, 1→3, 2→3 force a unique topological order [1,2,3].

nums (comma-separated)

seqs (rows ';' cells ',')

from collections import defaultdict, deque
def sequence_reconstruction(nums, seqs):
    adj = defaultdict(set)
    indeg = {v: 0 for v in nums}
    seen = set()
    for seq in seqs:
        for v in seq:
            if v not in indeg: return False
            seen.add(v)
        for a, b in zip(seq, seq[1:]):
            if b not in adj[a]:
                adj[a].add(b); indeg[b] += 1
    if len(seen) != len(nums): return False
    q = deque([v for v in nums if indeg[v] == 0])
    order = []
    while q:
        if len(q) > 1: return False
        v = q.popleft(); order.append(v)
        for nxt in adj[v]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0: q.append(nxt)
    return order == nums

function sequenceReconstruction(nums, seqs) {
  const adj = new Map(); const indeg = new Map();
  for (const v of nums) { adj.set(v, new Set()); indeg.set(v, 0); }
  const seen = new Set();
  for (const seq of seqs) {
    for (const v of seq) { if (!indeg.has(v)) return false; seen.add(v); }
    for (let i = 1; i < seq.length; i++) {
      const a = seq[i-1], b = seq[i];
      if (!adj.get(a).has(b)) { adj.get(a).add(b); indeg.set(b, indeg.get(b) + 1); }
    }
  }
  if (seen.size !== nums.length) return false;
  const q = nums.filter(v => indeg.get(v) === 0);
  const order = [];
  while (q.length) {
    if (q.length > 1) return false;
    const v = q.shift(); order.push(v);
    for (const nxt of adj.get(v)) {
      indeg.set(nxt, indeg.get(nxt) - 1);
      if (indeg.get(nxt) === 0) q.push(nxt);
    }
  }
  return order.length === nums.length && order.every((v, i) => v === nums[i]);
}

class Solution {
    public boolean sequenceReconstruction(int[] nums, List> seqs) {
        Map> adj = new HashMap<>();
        Map indeg = new HashMap<>();
        for (int v : nums) { adj.put(v, new HashSet<>()); indeg.put(v, 0); }
        Set seen = new HashSet<>();
        for (List seq : seqs) {
            for (int v : seq) { if (!indeg.containsKey(v)) return false; seen.add(v); }
            for (int i = 1; i < seq.size(); i++) {
                int a = seq.get(i - 1), b = seq.get(i);
                if (adj.get(a).add(b)) indeg.merge(b, 1, Integer::sum);
            }
        }
        if (seen.size() != nums.length) return false;
        Deque q = new ArrayDeque<>();
        for (int v : nums) if (indeg.get(v) == 0) q.add(v);
        List order = new ArrayList<>();
        while (!q.isEmpty()) {
            if (q.size() > 1) return false;
            int v = q.poll(); order.add(v);
            for (int nxt : adj.get(v)) {
                indeg.merge(nxt, -1, Integer::sum);
                if (indeg.get(nxt) == 0) q.add(nxt);
            }
        }
        if (order.size() != nums.length) return false;
        for (int i = 0; i < nums.length; i++) if (order.get(i) != nums[i]) return false;
        return true;
    }
}

bool sequenceReconstruction(vector& nums, vector>& seqs) {
    unordered_map> adj;
    unordered_map indeg;
    for (int v : nums) { adj[v]; indeg[v] = 0; }
    set seen;
    for (auto& seq : seqs) {
        for (int v : seq) { if (!indeg.count(v)) return false; seen.insert(v); }
        for (int i = 1; i < (int)seq.size(); i++) {
            int a = seq[i - 1], b = seq[i];
            if (adj[a].insert(b).second) indeg[b]++;
        }
    }
    if ((int)seen.size() != (int)nums.size()) return false;
    queue q;
    for (int v : nums) if (indeg[v] == 0) q.push(v);
    vector order;
    while (!q.empty()) {
        if (q.size() > 1) return false;
        int v = q.front(); q.pop(); order.push_back(v);
        for (int nxt : adj[v]) if (--indeg[nxt] == 0) q.push(nxt);
    }
    if ((int)order.size() != (int)nums.size()) return false;
    for (int i = 0; i < (int)nums.size(); i++) if (order[i] != nums[i]) return false;
    return true;
}

Explanation

Each subsequence tells us some "this comes before that" orderings. We turn those into a directed graph and ask: do these rules force exactly one valid ordering, and is it the given nums? We answer with Kahn's topological sort (BFS by in-degree).

For every consecutive pair a, b inside a subsequence we add an edge a → b and bump indeg[b]. The in-degree of a node is how many things must appear before it. We also confirm every value seen in the subsequences is a known node.

Kahn's algorithm repeatedly takes nodes with in-degree 0. The uniqueness test is the heart of it: at every step the queue must hold exactly one node. If two nodes ever have in-degree 0 at the same time, their relative order is ambiguous, so we return false. We pop that one node, append it to order, and decrement its neighbors' in-degrees.

Example: nums = [1,2,3], seqs = [[1,2],[1,3],[2,3]]. Edges 1→2, 1→3, 2→3 mean only 1 starts with in-degree 0, then only 2, then only 3 — a single forced order [1,2,3] matching the target, so true.

Finally we confirm the produced order equals nums. Unique order plus exact match is what makes the reconstruction valid.

Time: O(V + E) Space: O(V + E)