243 Shortest Word Distance

Given a list of words and two wordsword1andword2, return the shortest distance between these two words in the list.

For example, Assume that words =["practice", "makes", "perfect", "coding", "makes"].

Givenword1=“coding”,word2=“practice”, return 3. Givenword1="makes",word2="coding", return 1.

Note: You may assume thatword1does not equal toword2, andword1andword2are both in the list.

Attempt 1

  #include <iostream>
  #include <vector>
  #include <math.h>
  #include <algorithm>

  using namespace std;

  int shortestDistance(vector<string> *words, string word1, string word2)
  {

      vector<int> minElements;
      vector<int> word1Positions;
      vector<int> word2Positions;

      int word1Pos, word2Pos;
      int size = (*words).size();

      for (int i = 0; i < size; i++)
      {
          // store all positions of first word
          string currentWord = (*words).at(i);
          if (currentWord == word1)
              word1Positions.push_back(i);
          else if(currentWord == word2)
              word2Positions.push_back(i);
      }

      // find the minimum displacement between each word
      int difference;
      int j = 0;
      while (word2Positions.size() > j)
      {
          for (int i = 0; i < word1Positions.size(); i++)
          {
              difference = abs(((word1Positions).at(i)) - ((word2Positions).at(j)));
              minElements.push_back(difference);
          }
          j++;
      }

      int minElement = *min_element(minElements.begin(), minElements.end());
      cout << minElement << endl;
      return minElement;

  }

  int main()
  {
      vector<string> words = { "practice", "makes", "perfect", "coding", "makes" };

      string word1 = "coding", word2 = "practice"; // 3
      string word3 = "makes", word4 = "coding"; // 1

      shortestDistance(&words, word1, word2);
      shortestDistance(&words, word3, word4);
  }

Attempt 2: (12 ms, 92 percentile)

The Idea: First locate the occurrences of both words into two arrays. The shortest difference would then just be the minimum absolute difference between these two arrays. More specifically, it would be the minimum pair wise combination between the two arrays. We can perform two improvements here: first, since the arrays are sorted, we can binary search for the minimum difference. Secondly, we can scale better if we binary search on the larger array group. We know that we found the minimum difference when both the left and right side of the element produce a larger difference with the current key.

Complexity: O(NlogN) time, O(N) space

template<typename T>
int binary_search(vector<T> &nums, int low, int high, const T key, int prev_sol) {
    // if nothing was found then that means an equidistant element was ignored
    if (high < low) return prev_sol;

    int median = low + ((high - low) / 2);
    int med = nums.at(median);
    int left = median - 1 >= 0 ? nums.at(median - 1) : INT_MAX;
    int right = median + 1 < nums.size() ? nums.at(median + 1) : INT_MAX;
    int cur_diff = abs(med - key);

    // the center difference is smaller than both left and right differences
    // left and right are open
    if (left != INT_MAX && right != INT_MAX) {
        if (cur_diff < med - left && cur_diff < right - med)
            return cur_diff;

        // if the difference is smaller with the left element, then
        // we are bound to find a better improvement on the left
        if (abs(left - key) < cur_diff) {
            return binary_search(nums, low, median - 1, key, cur_diff);
        }

        // otherwise a word from the right must be closer
        else return binary_search(nums, median + 1, high, key, cur_diff);
    }
    // left is not open, right is
    else if (left == INT_MAX && right != INT_MAX) {
        if (cur_diff < abs(right - key))
            return cur_diff;
        return binary_search(nums, median + 1, high, key, cur_diff);
    }

    // left is open, right is not
    else if (left != INT_MAX && right == INT_MAX) {
        if (cur_diff < abs(left - key))
            return cur_diff;
        return binary_search(nums, low, median - 1, key, cur_diff);
    }
    // both left and right are closed
    else if (left == INT_MAX && right == INT_MAX) {
        return cur_diff;
    }    
}

int shortestDistance(vector<string>& words, string word1, string word2) {

    // store positions of target words
    vector<int> word1_pos, word2_pos;
    int counter = 0;

    for (string s : words) {
        if (s == word1) {
            word1_pos.push_back(counter);
        }
        else if (s == word2) {
            word2_pos.push_back(counter);
        }
        counter++;
    }

    // find the smallest absolute difference between every 
    // pair wise combination of two vectors
    int cur_min = INT_MAX;
    if (word1_pos.size() < word2_pos.size())
        for (int i : word1_pos) {
            int closest_word_index = binary_search(word2_pos, 0, word2_pos.size() - 1, i, -1);
            cur_min = min(cur_min, closest_word_index);
        }
    else
        for (int i : word2_pos) {
            int closest_word_index = binary_search(word1_pos, 0, word1_pos.size() - 1, i, -1);
            cur_min = min(cur_min, closest_word_index);
        }

    return cur_min;

}

Testing

int main()
{
    vector<string> words = { "practice", "makes", "perfect", "coding", "makes" };
    cout << shortestDistance(words, "coding", "practice") << endl; // 3
    cout << shortestDistance(words, "makes", "coding") << endl; // 1

    vector<string> words1 = { "b", "practice","practice","b", "practice", "makes", "perfect","makes", "coding", "makes", "a" };
    cout << shortestDistance(words1, "a", "b") << endl; // 7
    cout << shortestDistance(words1, "practice", "coding") << endl; // 4

    vector<string> words2 = { "a", "c", "b", "b", "a" };
    cout << shortestDistance(words2, "a", "b") << endl; // 1
}