2
$\begingroup$

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?

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

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;
$\endgroup$
2
  • 2
    $\begingroup$ 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? $\endgroup$
    – greybeard
    Jan 31 at 7:28
  • $\begingroup$ totally makes sense i will refactor my answer. $\endgroup$
    – frostcs
    Feb 13 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.