Restore the array from adjacent pairs

Array Hash Table Depth-First Search

75.1% acceptance

Feb 25, 2026

2050

There is an integer array nums that consists of n unique elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums. You are given a 2D integer array adjacentPairs of size n - 1 where each adjacentPairs[i] = [ui, vi] indicates that the elements ui and vi are adjacent in nums. It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will exist in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. Return the original array nums. If there are multiple solutions, return any of them.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn restore_array(adjacent_pairs: Vec<Vec<i32>>) -> Vec<i32> {
    let mut adj: HashMap<i32, Vec<i32>> = HashMap::new();
    for pair in &adjacent_pairs {
      adj.entry(pair[0]).or_default().push(pair[1]);
      adj.entry(pair[1]).or_default().push(pair[0]);
    }
    let n = adjacent_pairs.len() + 1;
    // Find an endpoint (degree 1)
    let start = *adj.iter().find(|(_, v)| v.len() == 1).unwrap().0;
    let mut result = vec![0i32; n];
    result[0] = start;
    if n > 1 {
      result[1] = adj[&start][0];
      for i in 2..n {
        let prev = result[i - 2];
        let cur = result[i - 1];
        result[i] = *adj[&cur].iter().find(|&&x| x != prev).unwrap();
      }
    }
    result
  }
}