Word Distance

PROBLEM STATEMENT

You are given a document as an Array/List 'ARR' of words of length ‘N’. You have to perform Q queries. In each query, you are given two words. Your task is to find the smallest distance between these two words in a document and return it.

Distance between words is defined as the difference between their indexes.

For example:

ARR=[‘hot’, ‘a’, ‘b’, ‘dog’] and query = (‘hot’, ‘dog’) 

The answer, in this case, is 3 as the minimum distance between ‘hot’ and ‘dog’ in the given document is 3.

Note:

If any one of the words is not present in the document then your program must return ‘N’ which is the length of the document.

Input Format:

The first line of input contains an integer 'T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains two space-separated integers, ‘N’ and ‘Q’ respectively.

The second line of each test case contains all the space-separated words in the document ARR.

The next ‘Q’ lines of each test case contain ‘Q’ queries, as two, space-separated words.

Output Format:

For each test case print ‘Q’ lines, i’th of which is the answer to i’th query.

Answer to each query is printed on a new line.

Note:

You don’t need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10^4
1 <= Q <=100

Where, ‘N’ and ‘Q’, are the length of the ARR, number of queries, respectively. 

All the strings in ARR contain only lowercase English letters. 

Time Limit: 1 sec

Approach 1

For each query, we will iterate over the entire document and keep two-pointer ‘PT1’ and ‘PT2’ for two words. If the current word of the document is equal to any of these two words we will update the answer and pointers.

The algorithm will be:

For each query:
1. Create two pointers ‘PT1’, ‘PT2’ initialize to -1 create ‘ANS’ and initialize to ‘N’.
2. For each word in ‘ARR’:
  - If the word is equal to the first word in the query:
    - Set ‘PT1’ to the current index.
  - If word equal to the second word in the query:
    - Set ‘PT2’ to the current index
  - If ‘PT1’ != -1 and ‘PT2’ !=-1
    - Set ANS to min( ‘ANS’, abs(‘PT2-PT1’) ).
3. Print ‘ANS’

Try Problem

Approach 2

For each word, we will store its indexes in the ‘ARR’. To answer a query we will iterate over these indexes and always increment an index that is behind. And minimize our ‘ANS’ with the differences between the two indexes.

The algorithm will be:

For each word create a list of its indexes in ‘ARR’ as ‘IDX’.
Now, for each query:
1. Create two pointers ‘PT1’, ‘PT2’ initialize to -1 create ‘ANS’ and initialize to ‘N’.
2. While ( ‘PT1’ < length of ‘IDX[first word]’ and ‘PT2’ < length of ‘IDX[second word]’)
  - Set ‘ANS’ to min( ‘ANS’, abs( ‘IDX[first word][PT1] - IDX[second word][PT2]’ )
  - If ( ‘IDX[fist word][PT1]’ < ‘IDX[second word][PT2]’ )
    - Increment ‘PT1’ by 1.
  - Else
    - Increment ‘PT2’ by 1.
3. Print the ‘ANS’.

Try Problem