How do you solve Restore the Array From Adjacent Pairs on LeetCode?

Restore the Array From Adjacent Pairs (LeetCode #1743) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The first element of the original array can be found by identifying the element that appears only once in the pairs.

What is the brute force solution for Restore the Array From Adjacent Pairs?

The brute force approach for Restore the Array From Adjacent Pairs is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves generating all possible permutations of the numbers and checking which one matches the adjacent pairs. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Restore the Array From Adjacent Pairs?

Restore the Array From Adjacent Pairs uses the following concepts: Array, Hash Table, Depth-First Search. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Restore the Array From Adjacent Pairs?

Always think about how to represent relationships in the problem; here, pairs can be represented as a graph. Start with a brute-force solution to understand the problem better before optimizing. Be prepared to explain your thought process and the reasoning behind your chosen approach.

What are common mistakes when solving Restore the Array From Adjacent Pairs?

Failing to recognize that the problem can be solved using graph traversal techniques. Not checking for edge cases, such as when the input has the minimum number of elements.

#1743

Restore the Array From Adjacent Pairs

Medium

ArrayHash TableDepth-First SearchHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal approach treats the adjacent pairs as edges in a graph. We can identify the starting point (the element that appears only once) and then perform a traversal (like DFS) to reconstruct the original array.

⚙️

Algorithm

3 steps

1Step 1: Create a graph (using a HashMap) where each key is an element and the value is a list of its adjacent elements.
2Step 2: Identify the starting element (it will have only one adjacent element).
3Step 3: Use Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the graph and build the original array.

solution.py20 lines

1from collections import defaultdict
2
3def restoreArray(adjacentPairs):
4    graph = defaultdict(list)
5    for u, v in adjacentPairs:
6        graph[u].append(v)
7        graph[v].append(u)
8    start = next(key for key in graph if len(graph[key]) == 1)
9    result = []
10    visited = set()
11
12    def dfs(node):
13        visited.add(node)
14        result.append(node)
15        for neighbor in graph[node]:
16            if neighbor not in visited:
17                dfs(neighbor)
18
19    dfs(start)
20    return result

ℹ

Complexity note: The time complexity is O(n) because we traverse each edge and node once in the graph. The space complexity is O(n) due to storing the graph and the result array.

1The first element of the original array can be found by identifying the element that appears only once in the pairs.
2The problem can be visualized as a graph where adjacent pairs represent edges.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.