Finding Minimum Distance Between Words in An Array

Question

Example:

WordDistanceFinder finder = new WordDistanceFinder(Arrays.asList("the", "quick", "brown", "fox", "quick"));

assert(finder.distance("fox","the") == 3);

assert(finder.distance("quick", "fox") == 1);

I have the following solution, which appears to be O(n), but I'm not sure if there is a better solution out there. Does anyone have any ideas?

String targetString = "fox";
String targetString2 = "the";
double minDistance = Double.POSITIVE_INFINITY;
for(int x = 0; x < strings.length; x++){
    if(strings[x].equals(targetString)){
        for(int y = x; y < strings.length; y++){
            if(strings[y].equals(targetString2))
                if(minDistance > (y - x))
                    minDistance = y - x;
        }
        for(int y = x; y >=0; y--){
            if(strings[y].equals(targetString2))
                if(minDistance > (x - y))
                    minDistance = x - y;
        }
    }
}

Answer 1

You solution is O(N^2) because you traverse the whole list when finding each word. First you find the first word and then again traverse the whole list to find the second word.

What you can do is use two variables to keep track of the position of each word and calculate the distance with a single pass through the list => O(N).

int index1 = -1;
int index2 = -1;
int minDistance = Integer.MAX_VALUE;
int tempDistance = 0;

for (int x = 0; x < strings.length; x++) {
    if (strings[x].equals(targetString)) {
        index1 = x;
    }
    if (strings[x].equals(targetString2)) {
        index2 = x;
    }
    if (index1 != -1 && index2 != -1) { // both words have to be found
        tempDistance = (int) Math.abs(index2 - index1);
        if (tempDistance < minDistance) {
            minDistance = tempDistance;
        }
    }
}

System.out.println("Distance:\t" + minDistance);

Answer 2

function findMinimumWordDistance(words, wordA, wordB) {
  var wordAIndex = null;
  var wordBIndex = null;
  var minDinstance = null;

  for (var i = 0, length = words.length; i < length; i++ ) {
    if (words[i] === wordA) {
      wordAIndex = i;
    }

    if (words[i] === wordB) {
      wordBIndex = i;
    }

    if ( wordAIndex !== null && wordBIndex !== null ) {
      var distance = Math.abs(wordAIndex - wordBIndex);
      if(minDinstance === null || minDinstance > distance) {
        minDinstance = distance;
      } 
    }
  }
  return minDinstance;
}