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.
1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4
5using namespace std;
6
7vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
8 unordered_map<int, vector<int>> adjMap;
9 for (const auto& pair : adjacentPairs) {
10 adjMap[pair[0]].push_back(pair[1]);
11 adjMap[pair[1]].push_back(pair[0]);
12 }
13
14 int start = 0;
15 for (const auto& [key, neighbors] : adjMap) {
16 if (neighbors.size() == 1) {
17 start = key;
18 break;
19 }
20 }
21
22 vector<int> result;
23 unordered_set<int> visited;
24 int prev = -1;
25
26 while (true) {
27 result.push_back(start);
28 visited.insert(start);
29 auto& neighbors = adjMap[start];
30 int next = -1;
31 for (const auto& neighbor : neighbors) {
32 if (neighbor != prev && visited.find(neighbor) == visited.end()) {
33 next = neighbor;
34 break;
35 }
36 }
37 if (next == -1) break;
38 prev = start;
39 start = next;
40 }
41
42 return result;
43}
44This C++ code uses unordered_map for storing adjacency information. It finds an appropriate starting point and uses a loop to reconstruct the array, ensuring visited nodes are tracked to avoid cycles or incorrect order.
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.