# Simulate merging of two sorted arrays - C++ solution, O(N) time, O(N) space

• I approached the "Shortest Word Distance I" problem already using the necessary auxiliary words positions map, so it wasn't a big deal to separate the logic between the constructor and main algorithm. The only thing I realized in addition to that is that we don't have to use set to sort the positions, since they are already inserted in a sorted order, so can just use vector.

``````  class WordDistance {
unordered_map<string, vector<size_t>> positions;
public:
WordDistance(vector<string>& words) {
for(size_t i = 0; i < words.size(); ++i) positions[words[i]].push_back(i);
}

int shortest(string word1, string word2) {
auto pos1 = positions[word1];
auto pos2 = positions[word2];

auto it1 = pos1.begin();
auto it2 = pos2.begin();

if(*it2 < *it1)
{
swap(it1, it2);
swap(pos1, pos2);
}

auto distance = *it2 - *it1;
auto last1 = *it1;
for(;;)
{
while(it1 != pos1.end() && *it1 <= *it2)
{
last1 = *it1;
++it1;
}
distance = min(*it2 - last1, distance);

if(it1 == pos1.end()) return distance;

swap(it1, it2);
swap(pos1, pos2);
}
return distance;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.