Restore the Array From Adjacent Pairs

medium graph hashing

Problem

You are given pairs of adjacent integers in an unknown array of distinct integers. Reconstruct any valid original array.

InputadjacentPairs = [[2,1],[3,4],[3,2]]

Output[1,2,3,4]

1 and 4 have one neighbor each — endpoints.

adjacent pairs (u,v;...)

def restore_array(adjacent_pairs):
    from collections import defaultdict
    adj = defaultdict(list)
    for a, b in adjacent_pairs:
        adj[a].append(b); adj[b].append(a)
    start = next(k for k, v in adj.items() if len(v) == 1)
    out = [start]
    prev = None
    while len(out) < len(adj):
        for x in adj[out[-1]]:
            if x != prev:
                prev = out[-1]
                out.append(x)
                break
    return out

function restoreArray(adjacentPairs) {
  const adj = new Map();
  for (const [a, b] of adjacentPairs) {
    if (!adj.has(a)) adj.set(a, []);
    if (!adj.has(b)) adj.set(b, []);
    adj.get(a).push(b); adj.get(b).push(a);
  }
  let start;
  for (const [k, v] of adj) if (v.length === 1) { start = k; break; }
  const out = [start];
  let prev = null;
  while (out.length < adj.size) {
    for (const x of adj.get(out[out.length - 1])) {
      if (x !== prev) { prev = out[out.length - 1]; out.push(x); break; }
    }
  }
  return out;
}

class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] p : adjacentPairs) {
            adj.computeIfAbsent(p[0], k -> new ArrayList<>()).add(p[1]);
            adj.computeIfAbsent(p[1], k -> new ArrayList<>()).add(p[0]);
        }
        int start = 0;
        for (var e : adj.entrySet()) if (e.getValue().size() == 1) { start = e.getKey(); break; }
        int[] out = new int[adj.size()];
        out[0] = start; int prev = Integer.MIN_VALUE;
        for (int i = 1; i < out.length; i++) {
            for (int x : adj.get(out[i-1])) if (x != prev) { prev = out[i-1]; out[i] = x; break; }
        }
        return out;
    }
}

vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
    unordered_map<int, vector<int>> adj;
    for (auto& p : adjacentPairs) { adj[p[0]].push_back(p[1]); adj[p[1]].push_back(p[0]); }
    int start = adj.begin()->first;
    for (auto& [k, v] : adj) if (v.size() == 1) { start = k; break; }
    vector<int> out(adj.size());
    out[0] = start; int prev = INT_MIN;
    for (int i = 1; i < (int)out.size(); i++) {
        for (int x : adj[out[i-1]]) if (x != prev) { prev = out[i-1]; out[i] = x; break; }
    }
    return out;
}

Explanation

Think of the original array as a chain: each value is linked to the value next to it. The adjacent pairs are just the links. If we rebuild those links, recovering the array is a matter of walking the chain from one end to the other.

First we build an adjacency list adj: for each pair [a, b] we record that a and b are neighbors of each other. Every middle value ends up with two neighbors, but the two ends of the array only have one neighbor each. So we pick any value whose list has length 1 as our start.

From the start we walk forward. We always keep track of the prev value we came from; at each step we move to the neighbor that isn't prev. That keeps us going straight down the chain instead of bouncing back.

Example: adjacentPairs = [[2,1],[3,4],[3,2]]. The lists are 1:[2], 2:[1,3], 3:[4,2], 4:[3]. Values 1 and 4 have one neighbor, so start at 1. Walk 1 → 2 → 3 → 4 to get [1, 2, 3, 4].

Since each step just looks at a short neighbor list and never revisits, the whole reconstruction is a single linear pass.

Time: O(n) Space: O(n)