Finding the minimum distance between words in an array

Question

Example:

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

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

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

I have the following solution that looks like O (n), but I'm not sure if there is a better solution 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

Your solution is O(N^2) because you are browsing the entire list when searching for each word. First you find the first word, and then go through the whole list again to find the second word.

What you can do is use two variables to track 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; } 

Answer 3

 import java.util.*; public class WordDistance { public static void main(String[] args) { Scanner in=new Scanner(System.in); String s=in.nextLine(); String s1=in.nextLine(); String s2=in.nextLine(); int index1=-1; int index2=-1; boolean flag1=false; boolean flag2=false; int distance=Integer.MAX_VALUE; int answer=Integer.MAX_VALUE; String[] sarray=s.split(" "); for(int i=0;i<sarray.length;i++) { if(!s1.equals(s2)) { flag1=false; flag2=false; } if(s1.equals(sarray[i]) && flag1==false) { index1=i; flag1=true; } else if(s2.equals(sarray[i]) && flag2==false) { index2=i; flag2=true; } if(index1!=-1 && index2!=-1) { distance=Math.abs(index1-index2); flag1=false; flag2=false; } if(distance<answer) { answer=distance; } } if(answer==Integer.MAX_VALUE) { System.out.print("Words not found"); } else { System.out.print(answer); } } } //**Test Case 1**: the quick the brown quick brown the frog (frog brown) **O/P 2** //**Test Case 2**: the quick the brown quick brown the frog (brown brown) **O/P 2** //**Test Case 3**: the brown qucik frog quick the (the quick) **O/P 1** 

Answer 4

The best and easiest solution to find the minimum distance between two words in this section.

  String[] strArray = {"the","quick","brown","fox","quick"}; String str1 = "quick"; String str2 = "fox"; int i,startIndex=0,minDistnace=100; for( i=0;i<strArray.length;i++){ if(strArray[i].equals(str1)||strArray[i].equals(str2)){ startIndex = i; //get the first occurence of either word break; } } for(;i<strArray.length;i++){ if(strArray[i].equals(str1)||strArray[i].equals(str2)){ //compare every word from that first occurence // if words not same and distance less than minimun distance then update if(!strArray[i].equals(strArray[startIndex]) && (i-startIndex)<minDistance){ minDistance = i-startIndex; startIndex =i; } else{ startIndex =i; } } } System.out.println(minDistance); 

Difficulty of time : O (n)
Space Maintenance : O (1)