Code Implementation

from collections import defaultdict

class Solution:
    def restoreArray(self, adjacentPairs):
        # Build adjacency list
        adj = defaultdict(list)
        for a, b in adjacentPairs:
            adj[a].append(b)
            adj[b].append(a)
        # Find the start (degree 1)
        for k in adj:
            if len(adj[k]) == 1:
                start = k
                break
        res = [start]
        prev = None
        curr = start
        while len(res) < len(adj):
            for neighbor in adj[curr]:
                if neighbor != prev:
                    res.append(neighbor)
                    prev, curr = curr, neighbor
                    break
        return res
      

class Solution {
public:
    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;
        for (auto& kv : adj) {
            if (kv.second.size() == 1) {
                start = kv.first;
                break;
            }
        }
        vector<int> res = {start};
        int prev = INT_MAX, curr = start;
        while (res.size() < adj.size()) {
            for (int neighbor : adj[curr]) {
                if (neighbor != prev) {
                    res.push_back(neighbor);
                    prev = curr;
                    curr = neighbor;
                    break;
                }
            }
        }
        return res;
    }
};
      

class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] pair : adjacentPairs) {
            adj.computeIfAbsent(pair[0], k -> new ArrayList<>()).add(pair[1]);
            adj.computeIfAbsent(pair[1], k -> new ArrayList<>()).add(pair[0]);
        }
        int start = 0;
        for (int key : adj.keySet()) {
            if (adj.get(key).size() == 1) {
                start = key;
                break;
            }
        }
        int n = adj.size();
        int[] res = new int[n];
        res[0] = start;
        int prev = Integer.MAX_VALUE, curr = start;
        for (int i = 1; i < n; ++i) {
            for (int neighbor : adj.get(curr)) {
                if (neighbor != prev) {
                    res[i] = neighbor;
                    prev = curr;
                    curr = neighbor;
                    break;
                }
            }
        }
        return res;
    }
}
      

var restoreArray = function(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.entries()) {
        if (v.length === 1) {
            start = k;
            break;
        }
    }
    const res = [start];
    let prev = null, curr = start;
    while (res.length < adj.size) {
        for (const neighbor of adj.get(curr)) {
            if (neighbor !== prev) {
                res.push(neighbor);
                prev = curr;
                curr = neighbor;
                break;
            }
        }
    }
    return res;
};
      

Problem Description

You are given a list of pairs called adjacentPairs, where each pair [u, v] means that the elements u and v are adjacent in some original array (but the order is unknown). Your task is to restore and return the original array.

Key details:

• Each adjacent pair appears exactly once in adjacentPairs (either as [u, v] or [v, u]).
• The original array contains all numbers from the pairs, without repeats.
• There is exactly one valid solution.
• You cannot reuse elements; the array must contain each number exactly once.

Thought Process

At first glance, the problem seems to require checking all possible orderings of the elements to see which one fits the adjacency requirements. However, this would be highly inefficient, especially for larger inputs.

Instead of brute-forcing all permutations, we can reason about the structure: each number is connected to its neighbors. If we think of the pairs as edges in a graph, the original array is like a path through the graph where each node (number) is connected to its neighbors.

The ends of the array (first and last elements) must have only one neighbor, while all other elements have two neighbors. This insight allows us to start from one end and reconstruct the array step by step, using the adjacency information.

Solution Approach

We can solve the problem efficiently by following these steps:

1. Build an adjacency list:
   • Create a mapping from each number to its neighboring numbers using a hash map (dictionary).
   • This allows us to quickly look up which numbers are adjacent to any given number.
2. Find a starting point:
   • Scan through the adjacency list to find a number with only one neighbor. This must be an end of the array (either the first or last element).
3. Reconstruct the array:
   • Start from the end element found in the previous step.
   • Iteratively add its neighbor to the result array, making sure not to revisit the immediate previous element (to avoid going backward).
   • Continue this process until all elements are added.
4. Return the reconstructed array.

We use a hash map for the adjacency list because it allows O(1) lookups when finding neighbors, making the overall process efficient.

Example Walkthrough

Let's work through an example with adjacentPairs = [[2,1],[3,4],[3,2]].

1. Build adjacency list:
   - 2: [1,3]
   - 1: [2]
   - 3: [4,2]
   - 4: [3]
2. Find an end:
   - 1 and 4 both have only one neighbor. Let's start with 1.
3. Reconstruct:
   - Start with 1. Its neighbor is 2.
   - Next, from 2 (neighbors: 1,3), skip 1 (already used), move to 3.
   - From 3 (neighbors: 4,2), skip 2, move to 4.
   - Now, we've used all elements: [1,2,3,4]
4. Result: [1,2,3,4]

At each step, we avoid going backward by skipping the element we just came from.

Time and Space Complexity

Brute-force approach:
- Trying all permutations would be O(N!), which is infeasible for large N.

Optimized approach (using adjacency list):

• Time Complexity: O(N), where N is the number of elements. We build the adjacency list in O(N), find the start in O(N), and reconstruct the array in O(N).
• Space Complexity: O(N), for storing the adjacency list and the result array.

Summary

The key insight for this problem is recognizing that the array's structure can be represented as a path in a graph, with the ends having only one neighbor. By building an adjacency list and starting from an endpoint, we can efficiently reconstruct the array in linear time. This approach avoids brute-force permutations and leverages the properties of adjacency to find the unique solution elegantly and efficiently.