Problem Source: LeetCode

Companies: LinkedIn, Microsoft, Paypal, Oracle.

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

### Example:

Assume that words = [“apple”, “oranges”, “mango”, “oranges”, “fruit”].

Input: word1 = “mango”, word2 = “apple”

Output: 2

Input: word1 = “oranges”, word2 = “fruit”

Output: 1

**Note:**

You may assume that word1 does not equal to word2, and word1 and word2 are both in the list.

### Solution:

This problem can be implemented easily using brute force but the time complexity will not be appreciable. But we can greatly improve brute force algorithm by iterating it only once and storing the latest indexes of the `word1`

and `word2`

. This means the time complexity is greatly reduced hence efficiency is maximized.

### Implementation

#### Java

public static class Solution { public int shortestDistance(String[] words, String word1, String word2) { int p = -1; int q = -1; int min = Integer.MAX_VALUE; for (int i = 0; i < words.length; i++) { if (words[i].equals(word1)) { p = i; } if (words[i].equals(word2)) { q = i; } if (p != -1 && q != -1) { min = Math.min(min, Math.abs(p - q)); } } return min; } }

### Complexity Analysis:

**Time Complexity:**O(n).**Space Complexity:**O(1).