Finding Minimum Distance Between Words in An Array

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 idea?

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

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);