Restore the Array From Adjacent Pairs
You have forgotten an integer array of n unique elements, but you remember every pair of adjacent elements. Given a 2D array adjacentPairs where each entry [u, v] means u and v were next to each other in the original array, your job is to reconstruct and return that original array.
This is LeetCode 1743: Restore the Array From Adjacent Pairs, and it is a great exercise in modeling a problem as a graph. Each number is a node, each pair is an edge, and the original array is just a path through that graph.
Why this problem matters
On the surface this looks like a pure array problem, but the trick is recognizing that adjacent pairs define an undirected graph. Once you see that, the problem becomes: "find a path that visits every node exactly once." Since the original array had unique elements and every pair of neighbors is given, the graph is guaranteed to be a simple chain (a path graph). That makes the traversal very clean.
This problem drills two essential skills. First, building an adjacency list from edge data, which is the foundation of nearly every graph algorithm. Second, identifying special nodes by their degree, which shows up in problems ranging from finding leaf nodes in trees to detecting articulation points in networks.
The key insight
Model the pairs as an undirected graph. Every number maps to a list of its neighbors. In the original array, the first and last elements each have exactly one neighbor (the element next to them). Every element in the middle has exactly two neighbors (the elements on either side).
So the algorithm is:
- Build an adjacency map from the pairs.
- Find any node with exactly one neighbor. That node is an endpoint of the original array.
- Starting from that endpoint, walk the chain. At each step, move to the neighbor that is not the node you just came from.
You never need a visited set. Because the graph is a simple chain, tracking just the previous node is enough to avoid going backwards.
The solution
from collections import defaultdict
def restore_array(adjacent_pairs: list[list[int]]) -> list[int]:
graph = defaultdict(list)
for u, v in adjacent_pairs:
graph[u].append(v)
graph[v].append(u)
start = next(node for node, neighbors in graph.items() if len(neighbors) == 1)
result = [start]
prev = None
curr = start
while len(result) < len(adjacent_pairs) + 1:
for neighbor in graph[curr]:
if neighbor != prev:
result.append(neighbor)
prev = curr
curr = neighbor
break
return result
Let's break this down.
The graph dictionary maps each number to its list of neighbors. We iterate through every pair and add both directions (u to v and v to u) because the relationship is symmetric.
Next, we scan the graph for any node with exactly one neighbor. That node must be an endpoint of the original array. We pick it as our starting point.
From there, we walk the chain. At each step, the current node has one or two neighbors. We pick the neighbor that is not the previous node and move forward. This continues until we have collected all n elements (which is len(adjacent_pairs) + 1, since n elements produce n-1 pairs).
You do not need a full visited set here. Since the graph is a simple path (no branches, no cycles), just remembering the previous node is enough to prevent backtracking. This keeps the logic minimal and avoids unnecessary overhead.
Visual walkthrough
Let's trace through the example with adjacentPairs = [[2,1],[3,4],[3,2]]. Watch how we build the adjacency map, pick a starting endpoint, and walk the chain to reconstruct [1, 2, 3, 4].
Step 1: Build the adjacency map from pairs
Each number maps to its neighbors. Endpoints (1 and 4) have exactly one neighbor.
Step 2: Find a node with degree 1 (only one neighbor)
Node 1 has only one neighbor (2), so it must be an endpoint. We pick it as our starting point.
Step 3: Begin at node 1, add it to result
result = [1]. Current = 1, previous = none. The only neighbor of 1 is 2, so move to 2.
Step 4: Move to node 2, add it to result
result = [1, 2]. Neighbors of 2 are [1, 3]. Skip 1 (previous), so move to 3.
Step 5: Move to node 3, add it to result
result = [1, 2, 3]. Neighbors of 3 are [4, 2]. Skip 2 (previous), so move to 4.
Step 6: Move to node 4, add it to result. Done!
result = [1, 2, 3, 4]. All nodes visited. The original array is restored.
The critical observation is in Step 2. Node 1 has only one neighbor (2), so it must be at one end of the original array. Node 4 also has degree 1, so it is at the other end. We could start from either one and get a valid answer.
Complexity analysis
| Metric | Value |
|---|---|
| Time | O(n) |
| Space | O(n) |
Time: Building the adjacency map takes O(n) since we process each of the n-1 pairs once. Finding the start node scans at most n entries. Walking the chain visits each node exactly once. Total: O(n).
Space: The adjacency map stores each number with its neighbor list. Since every number appears at most twice across all neighbor lists, the total storage is O(n). The result array also holds n elements. Total: O(n).
The building blocks
This problem is built on two reusable pieces that CodeBricks drills independently:
1. Building adjacency lists from edge data
The pattern of converting a list of edges into a graph representation:
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
This shows up in virtually every graph problem on LeetCode. Whether you are doing BFS, DFS, topological sort, or shortest path, the first step is almost always building an adjacency list. The key detail is remembering to add both directions for undirected edges. Miss one direction and your traversal will be incomplete.
2. Chain traversal with a previous pointer
The pattern of walking a linear structure while tracking where you came from:
prev = None
curr = start
while not_done:
for neighbor in graph[curr]:
if neighbor != prev:
prev = curr
curr = neighbor
break
This is simpler than a full visited set and works whenever the graph has no branches. You see the same idea in linked list traversal (tracking the previous node for reversal), in finding paths in trees (parent tracking), and in any linear chain problem. The discipline is always updating prev before moving curr forward.
If the graph had branches or cycles, tracking just the previous node would not be enough. You would need a full visited set. The reason this shortcut works here is that the problem guarantees the input forms a single simple path with no forks.
Edge cases
- Two elements, one pair: the simplest case. One pair
[a, b]gives you an array of length 2. Both nodes have degree 1. Return either[a, b]or[b, a]. - Already sorted pairs: if the pairs happen to describe a sorted array, the algorithm still works. It does not assume any ordering of the input pairs.
- Negative numbers: the values can be negative. The adjacency map handles them the same way since dictionary keys work with any hashable type.
- Large arrays (up to 10^5 elements): the O(n) solution handles this comfortably. No recursion depth issues since the traversal is iterative.
- Reversed pairs: a pair
[3, 2]is treated the same as[2, 3]because we add both directions. The order within each pair does not matter.
From understanding to recall
You see the pattern: build an adjacency map, find an endpoint, walk the chain. The logic is clean and the code is short. But under interview pressure, small details can trip you up. Forgetting to add both directions in the adjacency map. Using == instead of != when filtering out the previous node. Off-by-one on the loop condition (len(adjacent_pairs) + 1, not len(adjacent_pairs)).
Spaced repetition makes these details automatic. You practice building the adjacency map and walking the chain from memory at increasing intervals. After a few rounds, you do not need to think about whether to add 1 to the pair count. You just write it.
Related posts
- Clone Graph - DFS with a hash map for graph traversal, the same adjacency list pattern applied to deep copying
- Course Schedule - Directed graph traversal with topological sort, another problem where building the adjacency list is step one
- Reconstruct Itinerary - Rebuilding an ordered sequence from edge data, a harder variant of the same "reconstruct from pairs" idea
CodeBricks breaks Restore the Array From Adjacent Pairs into its adjacency-list-building and chain-traversal building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a graph reconstruction problem shows up in your interview, you do not hesitate. You just write it.