# Find original array from array with pairs of adjacent elements

Given an array composed of pairs, like this:

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

Each element in the array (call it pair) means that pair[0] and pair[1] are adjacent in the original array. Note, they can come in either order. For instance, for the sample array above, the original array would be:

4,1,5,3,2 (or the reversed version of this)

How can I do this quickly? I tried doing this as follows, which works, but it's too slow:

Create a hashmap that maps adjacent elements. Map = {3: [5,2], 1: [5,4], 5: [1,3], 4: [1], 2:[3]}. My algorithm would then start with one of the keys that only has a corresponding value length of 1 (in this case either 4 or 2), and then add to an output array, and go through the hashmap. I.e. First I would add 4 to my output, and then go from key of 4 (with a corresponding value of 1), to the key of 1, with corresponding values of 5 and 4. I'd ignore 4 (since it's already in output), and add 5, then go to the key of 5, and so on and so forth. This is too slow! Is there a better algorithm?

• This is too slow! Meaning? Your solution takes $O(n)$ time, i.e. it's asymptotically optimal.
– user114966
Jul 16 '20 at 23:23

Use indegree or DFS:

    unordered_map<int, int> indegree;
unordered_map<int, bool> visited;
unordered_map<int, vector<int>> mp;
mp[vect[0]].push_back(vect[1]);
mp[vect[1]].push_back(vect[0]);
indegree[vect[0]]++;
indegree[vect[1]]++;
}
int start = 0;
for (auto& in : indegree)
if (in.second == 1) {
start = in.first;
break;
}
}
int n = indegree.size();
vector<int> result;
result.push_back(start);
visited[start] = true;
while (result.size() != n) {
for (auto& val : mp[start]) {
if (!visited[val]) {
result.push_back(val);
visited[val] = true;
start = val;
}
}
}

return result;

• Welcome to COMPUTER SCIENCE @SE. Please consider how to present your idea without drawing on semantics (&syntax) of a concrete programming language. What can you say about the resource requirements of your suggestion? How does it differ from what James Flanagin suggests? Jan 31 at 7:28
• totally makes sense i will refactor my answer. Feb 13 at 13:16