Restore the Array From Adjacent Pairs

Restore the Array From Adjacent Pairs

What is this problem about?

The Restore the Array From Adjacent Pairs interview question gives you a 2D array of adjacent pairs from an original array (where each adjacent pair [a, b] means a and b were next to each other), and asks you to reconstruct the original array. The original array has no duplicates, and adjacent pairs are given in any order. Any valid reconstruction is acceptable.

Why is this asked in interviews?

This problem is asked at Visa, Meta, Roblox, SIG, Robinhood, Capital One, and Google because it tests graph construction and traversal. Recognizing that adjacent pairs define a path graph (each node has degree 1 or 2) allows a DFS/BFS traversal from a leaf (degree-1 node) to reconstruct the array. It evaluates a candidate's ability to model non-obvious problem structures as graphs.

Algorithmic pattern used

The pattern is graph construction followed by DFS path traversal. Build an adjacency list from the pairs. Identify a starting node: in the path graph, the two endpoints have degree 1 (they appear in only one pair). Start DFS from either endpoint. At each node, visit its unvisited neighbor and append it to the result. Continue until all nodes are visited. The traversal order gives the original array.

Example explanation

Adjacent pairs: [[2,1],[3,4],[3,2]]

Adjacency list:

• 2: [1, 3]
• 1: [2]
• 3: [4, 2]
• 4: [3]

Degree-1 nodes (endpoints): 1 (degree 1) and 4 (degree 1).

Start DFS from 1: 1 → 2 (unvisited) → 3 (unvisited) → 4 (unvisited).

Result: [1, 2, 3, 4].

Common mistakes candidates make

• Starting DFS from a non-endpoint (degree-2 node), which produces an incomplete or invalid traversal.
• Not marking nodes as visited, causing revisits and infinite loops.
• Building a directed graph when the pairs are undirected — always add both directions.
• Forgetting that if the array has length 1, it's a special case with no pairs.

Interview preparation tip

For the Restore the Array From Adjacent Pairs coding problem, the array, hash table, and DFS interview pattern is key. The insight — "treat adjacent pairs as edges in an undirected graph, find the endpoints, and traverse" — is the core problem reduction. Interviewers at Capital One and Robinhood appreciate when you state this graph modeling insight upfront before writing code. Practice identifying degree-1 nodes as the start of path traversal.