Problem Description

You need to restore an original integer array that contains n unique elements. You don't remember the array itself, but you have information about which elements were adjacent to each other.

Given:

• A 2D array adjacentPairs of size n-1 where each adjacentPairs[i] = [ui, vi] tells you that elements ui and vi were next to each other in the original array
• The pairs can be given in any order (either [a, b] or [b, a])
• Every consecutive pair from the original array is represented exactly once in adjacentPairs

Your task is to reconstruct and return the original array nums.

For example, if the original array was [1, 2, 3, 4], you might receive adjacent pairs like [[2,1], [3,4], [3,2]] which tells you:

• 2 and 1 were adjacent
• 3 and 4 were adjacent
• 3 and 2 were adjacent

From this information, you can deduce the original array was either [1, 2, 3, 4] or [4, 3, 2, 1] (both are valid solutions).

The key insight is that elements at the start and end of the array will only appear in one pair (they have only one neighbor), while all middle elements appear in exactly two pairs (they have two neighbors). The solution builds a graph of connections, finds a starting element (one with only one neighbor), and then traverses through the connections to rebuild the array.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves elements (nodes) and their adjacent relationships (edges). Each element in the array can be viewed as a node, and the adjacent pairs represent edges connecting these nodes.

Is it a tree?

• Yes: Since we have n unique elements and n-1 adjacent pairs that connect them all, this forms a tree structure (a connected acyclic graph). Additionally, the structure is linear - it's essentially a path graph where each node (except the endpoints) has exactly 2 neighbors.

DFS

• Yes: Based on the flowchart, when we have a tree structure, DFS is the recommended approach.

Conclusion: The flowchart suggests using DFS (Depth-First Search) for this problem.

This aligns perfectly with the solution approach:

1. Build a graph from the adjacent pairs where each node tracks its neighbors
2. Find a starting point (a node with only one neighbor - this must be an endpoint)
3. Use DFS traversal to reconstruct the array by following the connections from one element to the next, avoiding backtracking to already visited nodes

The DFS pattern is ideal here because we need to traverse through the entire connected structure exactly once, following the path from one endpoint to the other endpoint of the original array.

Intuition

The key observation is that when we have an array and know all adjacent pairs, we're essentially given the edges of a path graph. Think of it like a chain where each element is connected to its neighbors.

In any array, there are exactly two special elements - the first and last elements. These are special because they each have only one neighbor. All other elements in the middle have two neighbors (one on each side).

This gives us our starting point: if we count how many times each element appears in the adjacent pairs, the elements that appear only once must be the endpoints of our original array.

Once we identify an endpoint, we can start rebuilding the array like following a trail:

1. Start from one endpoint (it doesn't matter which one)
2. Move to its only neighbor
3. From there, we have two choices of where to go next, but one of them is where we just came from
4. Keep moving forward, always choosing the neighbor we haven't visited yet
5. Continue until we've reconstructed the entire array

For example, if we have pairs [[1,2], [2,3], [3,4]]:

• Element 1 appears once (neighbor: 2)
• Element 2 appears twice (neighbors: 1, 3)
• Element 3 appears twice (neighbors: 2, 4)
• Element 4 appears once (neighbor: 3)

So 1 and 4 are endpoints. Starting from 1, we go to 2, then to 3 (not back to 1), then to 4, giving us [1, 2, 3, 4].

This is essentially a DFS traversal along a linear path, where we maintain our direction by remembering where we came from and always moving to the unvisited neighbor.

Learn more about Depth-First Search patterns.

Solution Approach

The implementation follows a graph-based approach using an adjacency list and linear traversal:

Step 1: Build the Graph

g = defaultdict(list)
for a, b in adjacentPairs:
    g[a].append(b)
    g[b].append(a)

We create an adjacency list where each element maps to its neighbors. Since pairs can be given in any order [a,b] or [b,a], we add bidirectional edges. This gives us a graph where:

• Endpoint elements have exactly 1 neighbor
• Middle elements have exactly 2 neighbors

Step 2: Find a Starting Point

for i, v in g.items():
    if len(v) == 1:
        ans[0] = i
        ans[1] = v[0]
        break

We iterate through the graph to find any element with only one neighbor - this must be an endpoint. We place it at position 0 of our answer array and its only neighbor at position 1.

Step 3: Reconstruct the Array

for i in range(2, n):
    v = g[ans[i - 1]]
    ans[i] = v[0] if v[1] == ans[i - 2] else v[1]

Starting from position 2, we fill the rest of the array by:

• Looking at the previous element ans[i-1] and getting its neighbors v
• Since ans[i-1] has two neighbors (except for endpoints), one is where we came from ans[i-2] and the other is where we need to go next
• We select the neighbor that is NOT ans[i-2] as our next element

The algorithm has:

• Time Complexity: O(n) where n is the number of elements, as we process each pair once and traverse the array once
• Space Complexity: O(n) for storing the graph and the result array

This approach elegantly uses the graph structure to perform a directed traversal without needing explicit visited tracking, since we always know our previous position and can avoid backtracking.

Example Walkthrough

Let's walk through a concrete example with adjacentPairs = [[4,3], [1,4], [3,2]].

Step 1: Build the Graph

We create an adjacency list from the pairs:

• From [4,3]: Add 3 to 4's neighbors, add 4 to 3's neighbors
• From [1,4]: Add 4 to 1's neighbors, add 1 to 4's neighbors
• From [3,2]: Add 2 to 3's neighbors, add 3 to 2's neighbors

Our graph becomes:

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

Step 2: Find a Starting Point

Count neighbors for each element:

• Element 1: 1 neighbor (only 4) → This is an endpoint!
• Element 2: 1 neighbor (only 3) → This is also an endpoint
• Element 3: 2 neighbors (4 and 2) → Middle element
• Element 4: 2 neighbors (3 and 1) → Middle element

We pick element 1 as our starting point. Initialize our answer array of size 4:

• ans[0] = 1 (our starting endpoint)
• ans[1] = 4 (1's only neighbor)
• ans = [1, 4, ?, ?]

Step 3: Reconstruct the Array

Now we fill positions 2 and 3:

Position 2 (i=2):

• Previous element: ans[1] = 4
• 4's neighbors: [3, 1]
• Element two positions back: ans[0] = 1
• Since 1 is where we came from, we choose 3
• ans[2] = 3
• ans = [1, 4, 3, ?]

Position 3 (i=3):

• Previous element: ans[2] = 3
• 3's neighbors: [4, 2]
• Element two positions back: ans[1] = 4
• Since 4 is where we came from, we choose 2
• ans[3] = 2
• ans = [1, 4, 3, 2]

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

We can verify this is correct:

• 1 and 4 are adjacent ✓
• 4 and 3 are adjacent ✓
• 3 and 2 are adjacent ✓

Note that [2, 3, 4, 1] would also be a valid solution (the reverse order), which we'd get if we started from element 2 instead of element 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of elements in the original array (or len(adjacentPairs) + 1).

• Building the adjacency graph takes O(n-1) time since we iterate through all adjacent pairs once, and there are n-1 pairs for an array of length n.
• Finding the starting element (with degree 1) requires iterating through the graph dictionary, which has n unique elements, taking O(n) time in the worst case.
• Reconstructing the array requires iterating from index 2 to n-1, performing constant-time operations at each step (accessing the adjacency list and comparing values), which takes O(n) time.
• Overall: O(n-1) + O(n) + O(n) = O(n)

Space Complexity: O(n)

• The graph dictionary g stores all unique elements as keys, with each element appearing in exactly 2 pairs (except the endpoints which appear in 1 pair). This results in n keys with a total of 2(n-1) values stored across all adjacency lists, giving us O(n) space.
• The answer array ans stores exactly n elements, requiring O(n) space.
• Additional variables use O(1) space.
• Overall: O(n) + O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming Fixed Neighbor Order in Adjacency List

The most common pitfall occurs in the array reconstruction step when selecting the next element. Developers often assume a specific order of neighbors in the adjacency list:

Incorrect Assumption:

# WRONG: Assumes the unvisited neighbor is always at a specific index
for index in range(2, array_length):
    current_neighbors = adjacency_graph[result_array[index - 1]]
    result_array[index] = current_neighbors[0]  # Incorrectly assumes first neighbor is unvisited

Why This Fails: When we add edges bidirectionally to the graph, the order of neighbors in each list is arbitrary. For a middle element with neighbors [a, b], we cannot assume which one we've already visited based on their position in the list.

Correct Solution: Always explicitly check which neighbor was the previous element and select the other one:

for index in range(2, array_length):
    current_neighbors = adjacency_graph[result_array[index - 1]]
    # Explicitly check which neighbor is the previous element
    if current_neighbors[0] == result_array[index - 2]:
        result_array[index] = current_neighbors[1]
    else:
        result_array[index] = current_neighbors[0]

2. Not Handling Edge Cases with Small Arrays

Another pitfall is not considering arrays with only 2 elements:

Problem Scenario: If adjacentPairs = [[1, 2]], the array has only 2 elements. The reconstruction loop for i in range(2, n) won't execute at all.

Solution: The code handles this correctly by:

• Setting positions 0 and 1 before the loop
• The loop starting from index 2 only runs if n > 2
• For a 2-element array, the initial setup is sufficient

3. Using Set Instead of List for Neighbors

Some might try to optimize by using sets for the adjacency list:

# PROBLEMATIC: Using sets loses indexed access
adjacency_graph = defaultdict(set)

Why This Causes Issues: Sets don't support indexing (neighbors[0] or neighbors[1]), making it harder to implement the neighbor selection logic efficiently.

Better Approach: Stick with lists for simpler indexed access, or if using sets, convert to list when needed:

current_neighbors = list(adjacency_graph[result_array[index - 1]])