Sequence reconstruction

Array Graph Theory Topological Sort

30.6% acceptance

Mar 31, 2026

614

1548

No description available.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::VecDeque;

impl Solution {
  pub fn sequence_reconstruction(nums: Vec<i32>, sequences: Vec<Vec<i32>>) -> bool {
    let n = nums.len();
    let mut in_degree = vec![0i32; n + 1];
    let mut graph: Vec<Vec<usize>> = vec![vec![]; n + 1];
    // Track ordering constraints using a set to avoid duplicates
    let mut edges = std::collections::HashSet::new();

    for seq in &sequences {
      for w in seq.windows(2) {
        let u = w[0] as usize;
        let v = w[1] as usize;
        if edges.insert((u, v)) {
          graph[u].push(v);
          in_degree[v] += 1;
        }
      }
    }

    let mut queue = VecDeque::new();
    for i in 1..=n {
      if in_degree[i] == 0 {
        queue.push_back(i);
      }
    }

    let mut pos = vec![0usize; n + 1];
    for (idx, &x) in nums.iter().enumerate() {
      pos[x as usize] = idx;
    }

    let mut idx = 0;
    while let Some(node) = queue.pop_front() {
      // More than one candidate means not unique
      if queue.len() > 0 {
        return false;
      }
      if nums[idx] != node as i32 {
        return false;
      }
      idx += 1;
      for &next in &graph[node] {
        in_degree[next] -= 1;
        if in_degree[next] == 0 {
          queue.push_back(next);
        }
      }
    }

    idx == n
  }
}