Sponsored
Sponsored
In this approach, we will treat the problem as one of finding a path in a graph. Each element in the array is a node, and each adjacent pair represents an edge connecting two nodes. We can represent this graph using an adjacency list.
First, build the adjacency list from the given pairs. Elements with degree 1 (i.e., nodes with only one neighbor) are potential starting or ending points for the original array. We pick one such node and perform a depth-first search (DFS) or breadth-first search (BFS) to reconstruct the array.
Time Complexity: O(n), where n is the number of elements in nums.
Space Complexity: O(n), for storing the adjacency list and visited set.
1from collections import defaultdict
2
3def restoreArray(adjacentPairs):
4 adj_map = defaultdict(list)
5 for u, v in adjacentPairs:
6 adj_map[u].append(v)
7 adj_map[v].append(u)
8
9 # Find a starting point (it should have a single connection)
10 start = next(k for k, v in adj_map.items() if len(v) == 1)
11
12 # Restore the array by traversing
13 res = []
14 visited = set()
15 current = start
16 prev = None
17 while current is not None:
18 res.append(current)
19 visited.add(current)
20 neighbors = adj_map[current]
21 next_node = next((n for n in neighbors if n != prev), None)
22 prev = current
23 current = next_node
24
25 return res
26This Python solution constructs an adjacency list using defaultdict from the collections module. It picks a starting node with a single connection, then performs a traversal using a while loop to reconstruct the array. Nodes are marked as visited to avoid revisiting.
This approach builds the adjacency list similar to the previous one but uses sorting to aid in selecting the next node. While sorting might not always be the primary mechanism to solve the problem, it ensures adjacent nodes can be identified quickly, which helps in managing which node to process next in the construction of the resultant array.
Time Complexity: O(n). Space Complexity: O(n), for maintaining necessary data structures.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] RestoreArray(int[][] adjacentPairs) {
6 var adjMap = new Dictionary<int, List<int>>();
7
8 // Build the adjacency map
foreach (var pair in adjacentPairs) {
if (!adjMap.ContainsKey(pair[0])) adjMap[pair[0]] = new List<int>();
if (!adjMap.ContainsKey(pair[1])) adjMap[pair[1]] = new List<int>();
adjMap[pair[0]].Add(pair[1]);
adjMap[pair[1]].Add(pair[0]);
}
// Find the start of the array
int start = 0;
foreach (var kvp in adjMap) {
if (kvp.Value.Count == 1) {
start = kvp.Key;
break;
}
}
// Reconstruct the array
List<int> result = new List<int>();
HashSet<int> visited = new HashSet<int>();
int prev = -1;
while (true) {
result.Add(start);
visited.Add(start);
var neighbors = adjMap[start];
int next = -1;
foreach (var neighbor in neighbors) {
if (neighbor != prev && !visited.Contains(neighbor)) {
next = neighbor;
break;
}
}
if (next == -1) break;
prev = start;
start = next;
}
return result.ToArray();
}
}
The C# solution is similar in spirit to the earlier ones. It builds a dictionary for adjacency mapping and rebuilds the array by picking nodes not yet visited. It emphasizes cleanliness and direct approach instead of relying on complex loops or conditional checks.