### Problem Statement

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 =

`["practice", "makes", "perfect", "coding", "makes"]`

.Input:word1=`“coding”`

,word2=`“practice”`

Output:3

Input:word1=`"makes"`

,word2=`"coding"`

Output:1

**Note:**

You may assume that

*word1*

**does not equal to**

*word2*, and

*word1*and

*word2*are both in the list.

### Video Tutorial

You can find the detailed video tutorial here### Thought Process

It is a bit confusing at first to be confused with the "Edit Distance" problem. However, there are duplicate words in the array, it's just a matter of finding the minimum distance between two words, where words could be found in multiple places in the array.Brute force way (for each word, find the closest distance with the other word) would give you O(N^2) time complexity where N is the array size. An O(N) optimization would be having two indices for each word and keep updating the minimum distance. It is greedy because the closer the two elements are, the smaller the distance would be.

You can refer to Leetcode official solution for a detailed explanation.

### Solutions

#### Implementation

Time Complexity: O(N) where N is the array sizeSpace Complexity: O(1) Constant space

References