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

Doerr

That solution is O(n^2) -- you have nested for loops. And yes, this can be done in O(n), but I'm pretty sure this is homework, so that's all I'll say for now. – Santossantosdumont

It's an interview question. – Doerr

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

Puncture

A major problem: Words are allowed to appear more than once (look at the example problem instance), but this code makes no attempt to consider any but the last occurrence. A minor problem: Because you wrote else if instead of just if, this won't work if targetString == targetString2. – Santossantosdumont

Well if words are allowed to appear more than once then its its implementation based how to handle this as in, which one of the duplicates to pick as the start/end. I am not sure why you gave me a -1 – Puncture

For starters, the example contains "quick" twice. But more generally, if you're given a problem description, you can't just assume constraints that aren't given in the problem! – Santossantosdumont

I gave you the -1 because your code gives the wrong answer sometimes -- specifically, when the nearest occurrences of the 2 input words are not the last occurrence of each. – Santossantosdumont

I see you have updated your post, but offering the programmer or user the ability to choose which occurrence doesn't solve the problem: "What is the minimum distance between the two given words?" The task is to make the program choose the right occurrences. – Santossantosdumont

saw what my issue was, i believe i fixed it. thanks for the pointers – Puncture

Almost there, but initializing minDistance to -1 won't work, because then your last if will never be true. Also, why are you using double? – Travertine

@ajb: Good points. minDistance. should start out at INT_MAX, or whatever it's called in Java. – Santossantosdumont

Its all fixed :) I was rushing to answer quickly and i missed the initialization. To answer @ajb's question, I was using double because its a habit when using the Math class :). Thanks for the pointers fellas – Puncture

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

Watterson

function findMinimumWordDistance(words, wordA, wordB) Some Java. – Astrology

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**

Myrnamyrobalan

Answer 4

Better and simple solution for finding minimum distance between two words in a given paragraph.

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

Time Complexity: O(n)
Space COmplexity: O(1)

Prather

I doubt this compiles. Once corrected, how is it better than nem035's 2014 answer? – Astrology

Answer 5

Just 1 iteration. Very Simple Solution Assumptions : str1 and str2 are not null. str1 not equal to str2. strs does not contains null;

    private static int findShortestDistance(String str1, String str2, String[] strs) {
        int distance = Integer.MAX_VALUE;
        String temp = null;
        int index = 0;
        for(int i=0; i<strs.length; ++i) {
          if(str1.equals(strs[i]) || str2.equals(strs[i])) {
             if(temp != null && !strs[i].equals(temp)) {
                distance = Math.min(distance, i - index);
             }
             temp = strs[i];
             index = i;
           }
        }
     return distance;
    }

Ilbert

findShortestDistance("the", "fox", new String[]{"the", "the", "quick", "brown", "fox", "quick") – Astrology

Answer 6

  private static Integer getDistance(String first, String second, String given) {
    String[] splitGiven = given.split(" ");
    int firstWord;
    int secondWord;
    int result;
    List<Integer> suspectedDistances = new ArrayList<>();
    for (int i = 0; i < splitGiven.length; i++) {
      if (Objects.equals(splitGiven[i], first)) {
        firstWord = i;
       
        for (int j = 0; j < splitGiven.length; j++) {
          if (Objects.equals(splitGiven[j], second)) {
            secondWord = j;
            
            suspectedDistances.add(secondWord - firstWord);
          }
        }
      }
    }
  
    Collections.sort(suspectedDistances);
    result = suspectedDistances.get(0);
    if ((splitGiven[0].equals(first) || splitGiven[0].equals(second)) &&
        (splitGiven[splitGiven.length - 1].equals(first) || splitGiven[splitGiven.length - 1].equals(second))) {
      result = 1;
    }
    return result;
  }

Schoolman

above solution for : write a function that will return the minimum distance between the two words from a given string. Adjacent words will have a distance of 1. – Schoolman

From java.util.Collections, sorting to just get the minimum (or maximum) is costly. Can you spot something more direct in the documentation? (Other answers avoid collecting distances.) – Astrology

above solution for […] return the minimum distance between the two words from a given string Document getDistance() in your code. Edit your post to add information. – Astrology

Answer 7

any ideas?

You "duplicated" code: Keep DRY: Don't Repeat Yourself

double
    distance,
    minDistance = Double.POSITIVE_INFINITY;
for (int x = 0 ; x < strings.length ; x++)
    if (strings[x].equals(targetString))
        for (int y = 0 ; y < strings.length ; y++)
            if (x != y && strings[y].equals(targetString2)) {
                if (minDistance > (distance = Math.abs(y - x)))
                    minDistance = distance;
                if (x < y)
                    break;
            }

You missed opportunities to stop iterating early:

minDistance = strings.length;
if (java.util.Arrays.asList(strings).contains(targetString2))
    for (int x = 0 ; x < strings.length ; x++) {
        if (!strings[x].equals(targetString))
            continue;
        for (int y = x, limit = Math.min(strings.length, x + minDistance) ; ++y < limit ; )
            if (strings[y].equals(targetString2)) {
                minDistance = y - x;
                break;  // higher values of y won't decrease y - x
            }
        for (int y = x, limit = Math.max(-1, x - minDistance) ; limit < --y ; )
            if (strings[y].equals(targetString2)) {
                minDistance = x - y;
                break;  // lower values of y won't decrease x - y
            }
        if (minDistance < 2)
            break;
    }

Astrology

Answer 8

With only one while loop without any DS and internal method like Math class etc. Time complexity: O(n) PFB the code:

public class MinimumDistanceBetweenTheGivenTwoWords {
private void minimumDistanceBetweenTwoWords(String[] statement, String word1, String word2) {

 int firstCounter=0; int secondCounter=0;
 int i=0;
 while (i<statement.length-1){
     if(statement[i].equalsIgnoreCase(word1)){
         firstCounter = i;
     }
     if(statement[i+1].equalsIgnoreCase(word2)){
         secondCounter = i+1;
     }
     i++;
 }
    int shortestDistance = secondCounter-firstCounter;
    System.out.println("Shortest distance: "+shortestDistance);
}

public static void main(String[] args) {
    MinimumDistanceBetweenTheGivenTwoWords obj = new MinimumDistanceBetweenTheGivenTwoWords();
    String[] statement = {"the", "quick", "brown", "fox", "quick"};
    obj.minimumDistanceBetweenTwoWords(statement1, "the", "fox");
}
}

Mestee