# 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 and pair 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: , 2:}. 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].push_back(vect);
mp[vect].push_back(vect);
indegree[vect]++;
indegree[vect]++;
}
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