Find original array from array with pairs of adjacent elements

Question

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?

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

Answer 1

Use indegree or DFS:

 unordered_map<int, int> indegree;
 unordered_map<int, bool> visited;
 unordered_map<int, vector<int>> mp;
 for (auto& vect: adjacentPairs) {
 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;

• greybeard: 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?
• frostcs: totally makes sense i will refactor my answer.