LeetCode 1743 - Restore the Array From Adjacent Pairs

LeetCode Problem 1743

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Depth-First Search

Solution

Problem Understanding

The problem gives us all adjacent pairs from an unknown array nums, and our task is to reconstruct the original array.

Suppose the original array was:

[1, 2, 3, 4]

The adjacent pairs would be:

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

The important detail is that the pairs can appear in any order and can also be reversed. So the input might look like:

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

Even though the ordering is scrambled, the adjacency relationships still fully describe the original array.

The array contains unique integers, which is extremely important. Because every value is unique, each number can only appear in specific positions in the array. In a valid linear array:

• Interior elements have exactly two neighbors.
• The two endpoints have exactly one neighbor.

This immediately suggests a graph interpretation. Each number is a node, and each adjacent pair creates an undirected edge between two nodes. Since the original array forms a simple chain, the resulting graph is a path graph.

The constraints are large:

• n can be as large as 10^5
• We must process up to 100000 pairs efficiently

This rules out expensive backtracking or repeated scanning approaches. We need a solution close to linear time.

There are several important edge cases:

• The array may contain negative numbers.
• The array may contain only two elements.
• The adjacent pairs may be presented in completely random order.
• Either valid reconstruction direction is acceptable. For example, [1,2,3] and [3,2,1] are both correct.
• We must avoid revisiting elements while reconstructing the path.

Because the problem guarantees a valid solution exists, we do not need to handle malformed graphs or disconnected components.

Approaches

Brute Force Approach

A brute force solution would attempt to rebuild the array by trying every possible starting element and recursively extending the sequence using unused adjacent pairs.

At each step, we would search for a pair containing the current number, append the matching neighbor, mark that pair as used, and continue until all elements are reconstructed.

This approach is correct because it explores all possible valid paths through the adjacency relationships. Eventually, it will discover the original ordering.

However, this becomes extremely inefficient for large inputs. Every recursive step may scan many pairs, and the branching factor can grow significantly. In the worst case, the time complexity becomes quadratic or worse.

With 10^5 elements, this approach is far too slow.

Optimal Approach

The key observation is that the adjacent relationships form a path graph.

In a path graph:

• Exactly two nodes have degree 1, these are the endpoints.
• Every other node has degree 2.

We can therefore:

1. Build an adjacency list using a hash map.
2. Find one endpoint by locating a node with only one neighbor.
3. Walk through the chain sequentially, always choosing the next unvisited neighbor.

Because each node is processed once, the solution becomes linear.

This works perfectly because the graph structure is guaranteed to represent a single valid array.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²) or worse	O(n)	Repeatedly scans pairs and explores paths
Optimal	O(n)	O(n)	Uses adjacency list and linear traversal

Algorithm Walkthrough

1. Create an adjacency list using a hash map.

For every pair [u, v], add:

• v to u's neighbor list
• u to v's neighbor list

This converts the input into an undirected graph representation. 2. Find a starting node.

In the original array, the two endpoints each have only one neighbor. Therefore, in the adjacency list, endpoints have degree 1.

We iterate through the hash map and select any node whose neighbor list length is 1. 3. Initialize the result array.

Add the starting endpoint as the first element of the answer. 4. Track the previous element.

During traversal, each interior node has two neighbors:

• the node we came from
• the node we should go to next

To avoid going backward, we keep track of the previous node. 5. Reconstruct the array sequentially.

At each step:

• Look at the current node's neighbors.
• Choose the neighbor that is not equal to the previous node.
• Append it to the result.
• Move forward.

6. Continue until all nodes are added.

Since the graph is a simple chain, we eventually visit every node exactly once.

Why it works

The graph formed by the adjacent pairs is guaranteed to be a single path. A path graph has exactly two endpoints with degree 1, and every other node has degree 2.

Starting from either endpoint and repeatedly moving to the neighbor that is not the previously visited node uniquely reconstructs the path. Since every node is visited exactly once, the resulting sequence is a valid reconstruction of the original array.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        graph = defaultdict(list)

        # Build adjacency list
        for u, v in adjacentPairs:
            graph[u].append(v)
            graph[v].append(u)

        # Find endpoint
        start = None
        for node, neighbors in graph.items():
            if len(neighbors) == 1:
                start = node
                break

        n = len(adjacentPairs) + 1
        result = [0] * n
        result[0] = start

        # Handle array of length 2
        if n == 2:
            result[1] = graph[start][0]
            return result

        # Second element must be the only neighbor of start
        result[1] = graph[start][0]

        # Reconstruct remaining elements
        for i in range(2, n):
            neighbors = graph[result[i - 1]]

            # Choose neighbor different from previous element
            if neighbors[0] == result[i - 2]:
                result[i] = neighbors[1]
            else:
                result[i] = neighbors[0]

        return result

The implementation begins by constructing an adjacency list using defaultdict(list). This allows constant time insertion of neighbors while naturally representing the graph structure.

Next, the code searches for an endpoint. Since endpoints have exactly one neighbor, we simply locate a node whose adjacency list has length 1.

The result array is then initialized with the starting endpoint. If the array length is only two, reconstruction is trivial because the endpoint's only neighbor must be the second element.

For larger arrays, the second element is uniquely determined because the starting endpoint has only one neighbor.

From that point onward, every interior node has two neighbors. One neighbor is the previous element in the reconstructed sequence, while the other is the next element we need. By comparing against the previous value, we can determine which neighbor to append next.

The traversal continues until the entire array is reconstructed.

Go Solution

package main

func restoreArray(adjacentPairs [][]int) []int {
	graph := make(map[int][]int)

	// Build adjacency list
	for _, pair := range adjacentPairs {
		u, v := pair[0], pair[1]

		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	// Find endpoint
	start := 0
	for node, neighbors := range graph {
		if len(neighbors) == 1 {
			start = node
			break
		}
	}

	n := len(adjacentPairs) + 1
	result := make([]int, n)

	result[0] = start

	// Handle length 2
	if n == 2 {
		result[1] = graph[start][0]
		return result
	}

	// Second element
	result[1] = graph[start][0]

	// Reconstruct array
	for i := 2; i < n; i++ {
		neighbors := graph[result[i-1]]

		if neighbors[0] == result[i-2] {
			result[i] = neighbors[1]
		} else {
			result[i] = neighbors[0]
		}
	}

	return result
}

The Go implementation follows the same logic as the Python solution. A map[int][]int is used for the adjacency list.

Slices naturally represent neighbor lists efficiently. Since every interior node has exactly two neighbors, accessing neighbors[0] and neighbors[1] is safe after the initial setup.

No special handling for integer overflow is needed because the constraints fit comfortably within Go's int type.

Worked Examples

Example 1

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

Step 1: Build adjacency list

Pair	Graph State
[2,1]	2:[1], 1:[2]
[3,4]	3:[4], 4:[3]
[3,2]	3:[4,2], 2:[1,3]

Final graph:

1 -> [2]
2 -> [1,3]
3 -> [4,2]
4 -> [3]

Step 2: Find endpoint

Nodes 1 and 4 each have degree 1.

Choose:

start = 1

Step 3: Reconstruct array

Index	Current Result	Explanation
0	[1]	Start endpoint
1	[1,2]	Only neighbor of 1
2	[1,2,3]	From neighbors [1,3], skip previous 1
3	[1,2,3,4]	From neighbors [4,2], skip previous 2

Final answer:

[1,2,3,4]

Example 2

adjacentPairs = [[4,-2],[1,4],[-3,1]]

Step 1: Build adjacency list

4  -> [-2,1]
-2 -> [4]
1  -> [4,-3]
-3 -> [1]

Step 2: Find endpoint

Possible endpoints:

-2 or -3

Choose:

start = -2

Step 3: Reconstruct array

Index	Current Result
0	[-2]
1	[-2,4]
2	[-2,4,1]
3	[-2,4,1,-3]

Final answer:

[-2,4,1,-3]

Example 3

adjacentPairs = [[100000,-100000]]

Step 1: Build adjacency list

100000  -> [-100000]
-100000 -> [100000]

Step 2: Find endpoint

Either node is valid.

Choose:

start = 100000

Step 3: Reconstruct array

Index	Current Result
0	[100000]
1	[100000,-100000]

Final answer:

[100000,-100000]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each edge and node is processed a constant number of times
Space	O(n)	The adjacency list stores all nodes and edges

The adjacency list construction processes each adjacent pair once. The traversal phase also visits each node exactly once. Since all operations on the hash map are average O(1), the total runtime is linear.

The space usage is linear because the graph stores every node and edge. The result array also requires O(n) space.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        graph = defaultdict(list)

        for u, v in adjacentPairs:
            graph[u].append(v)
            graph[v].append(u)

        start = None
        for node, neighbors in graph.items():
            if len(neighbors) == 1:
                start = node
                break

        n = len(adjacentPairs) + 1
        result = [0] * n
        result[0] = start

        if n == 2:
            result[1] = graph[start][0]
            return result

        result[1] = graph[start][0]

        for i in range(2, n):
            neighbors = graph[result[i - 1]]

            if neighbors[0] == result[i - 2]:
                result[i] = neighbors[1]
            else:
                result[i] = neighbors[0]

        return result

def valid(arr, pairs):
    actual = set()

    for i in range(len(arr) - 1):
        a, b = arr[i], arr[i + 1]
        actual.add(tuple(sorted((a, b))))

    expected = set(tuple(sorted(pair)) for pair in pairs)

    return actual == expected

sol = Solution()

# Example 1
pairs = [[2,1],[3,4],[3,2]]
result = sol.restoreArray(pairs)
assert valid(result, pairs)  # basic reconstruction

# Example 2
pairs = [[4,-2],[1,4],[-3,1]]
result = sol.restoreArray(pairs)
assert valid(result, pairs)  # negative numbers

# Example 3
pairs = [[100000,-100000]]
result = sol.restoreArray(pairs)
assert valid(result, pairs)  # smallest valid input

# Simple increasing chain
pairs = [[1,2],[2,3],[3,4],[4,5]]
result = sol.restoreArray(pairs)
assert valid(result, pairs)  # straightforward chain

# Reverse ordering of pairs
pairs = [[5,4],[4,3],[3,2],[2,1]]
result = sol.restoreArray(pairs)
assert valid(result, pairs)  # reversed edges

# Random order
pairs = [[10,20],[30,40],[20,30]]
result = sol.restoreArray(pairs)
assert valid(result, pairs)  # unordered input pairs

# Large negative and positive mix
pairs = [[-100000,0],[0,100000]]
result = sol.restoreArray(pairs)
assert valid(result, pairs)  # boundary values

# Two element array
pairs = [[7,8]]
result = sol.restoreArray(pairs)
assert valid(result, pairs)  # minimal size

# Longer chain
pairs = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]
result = sol.restoreArray(pairs)
assert valid(result, pairs)  # larger linear chain

print("All tests passed.")

Test	Why
[[2,1],[3,4],[3,2]]	Basic reconstruction example
[[4,-2],[1,4],[-3,1]]	Verifies handling of negative numbers
[[100000,-100000]]	Smallest valid input size
Increasing chain	Standard ordered structure
Reverse ordering	Ensures direction does not matter
Random order	Confirms adjacency list reconstruction
Large value mix	Tests boundary integer values
Two element array	Important minimal edge case
Longer chain	Verifies traversal across many nodes

Edge Cases

One important edge case is when the original array contains only two elements. In this scenario, both nodes are endpoints, and each node has exactly one neighbor. A careless implementation may attempt to access a second neighbor that does not exist. The solution handles this explicitly with a special case for n == 2.

Another important edge case involves negative integers. Since the values can range from -10^5 to 10^5, implementations that incorrectly rely on array indexing instead of hash maps may fail or waste large amounts of memory. Using a hash map allows the algorithm to handle arbitrary integer values naturally.

A third critical edge case is the arbitrary ordering of adjacent pairs. The input pairs are not guaranteed to appear in traversal order. A naive implementation that assumes local ordering from the input would break immediately. The adjacency list representation completely avoids this issue because it stores relationships independent of input ordering.

A subtle edge case occurs during traversal of interior nodes. Each interior node has two neighbors, and choosing the wrong one causes the traversal to move backward instead of forward. The implementation avoids this by always comparing against the previously visited element and selecting the other neighbor.

Finally, the graph can be reconstructed from either endpoint, producing either the original array or its reverse. Since the problem accepts any valid reconstruction, the algorithm simply picks the first endpoint it encounters.